安全多方计算及其扩展问题的研究

摘要

安全多方计算是分布式系统和密码学及其应用的研究基础，几乎所有的密码学装置（如加密、认证、协商、签名等）和分布式场景（如电子投票、电子拍卖、隐私信息检索、隐私保护数据挖掘等）都可视为安全多方计算的特例。在安全多方计算中，拥有隐私信息的两个或多个参与方想要联合完成由他们的隐私信息所决定的某种计算。该计算不仅要保证各方都能够得到正确的输出（正确性），而且还要保证任何一方都得不到除了自己的合理输出之外的任何信息（安全性）。
　　 本文主要讨论了映射比较问题、数据比较问题和分布式线性代数问题这三类具体的安全多方计算问题，提出了安全多方计算的一个扩展问题（即代理多方计算问题）并作了进一步的相关的研究。本论文的创新工作如下：
　　 （1）提出了一个新的安全双方计算问题，即映射相等问题（在保护隐私的情况下判断两个映射是否相等）。利用全变换半群基础理论作为基本的分析工具，将可交换的确定型加密体制作为基本的密码学原语，构建了求解映射相等问题的安全计算协议。由此看出全变换半群基础理论在安全计算协议的研究中有一定的应用，进一步的，本论文在数学意义下对全变换半群基础理论作了一些研究：提出了全变换半群的一类子半群，即保E-序全变换半群，并对有限的情形研究了此类半群的正则性和Green关系。另外，考虑了映射相等问题的特殊问题，即变换相等问题（在保护隐私的情况下判断两个变换是否相等），并分别将健忘传输协议和同态加密体制作为基本的密码学原语，构建了此问题的两个解决方案。
　　 （2）Yao氏百万富翁问题（在保护隐私的情况下比较两个整数的大小）和广义百万富翁问题（在保护隐私的情况下比较两个实数的大小）是两个主要的安全双方计算问题。最近，解决这两个问题的对称密码解分别被提出：通过构建集合包含问题的一个对称密码解并将其作为基本的构建模块，提出了Yao氏百万富翁问题的一个对称密码解；通过构建成员判定问题的一个对称密码解并将其作为基本的构建模块，提出了广义百万富翁问题的一个对称密码解。本论文对上述对称密码解进行了分析，证明了集合包含问题的对称密码解和成员判定问题的对称密码解都是不完善的（即严格执行协议之后，可能会输出错误的判断结果），从而说明了Yao氏百万富翁问题的对称密码解和广义百万富翁问题的对称密码解都是不完善的（即严格执行协议之后，可能会输出错误的比较结果）。将语义安全的同态加密体制作为基本的密码学原语，分别构建了求解集合包含问题（从而求解Yao氏百万富翁问题）和求解广义百万富翁问题的解决方案。
　　 （3）研究了两个分布式线性代数问题：（3-1）提出了一个新的安全多方计算问题，即向量组秩和极大线性无关组问题（在保护隐私的情况下计算向量组的秩和全部极大线性无关组），并分别将健忘传输协议和同态加密体制作为基本的密码学原语，构建了此问题的两个解决方案；（3-2）研究了仿射子空间交问题（在保护隐私的情况下计算有限域F上的两个仿射子空间的交），并将健忘传输协议和同态加密体制作为基本的密码学原语，构建了此问题的一个解决方案。
　　 （4）提出了安全多方计算的一个扩展问题，即代理多方计算问题（仅涉及两方时称为代理双方计算问题）：在安全多方计算的一次执行中，每个参与者都可以在不不失隐私性的情况下将其计算能力委托给它的代理人，从而达到安全计算的目的。定义了代理多方计算的相关模型，特别地，在半诚实攻击者模型下定义了代理多方计算的安全模型。作为具体实例，研究了两个代理分布式线性代数问题：（4-1）将安全多方向量组秩和极大线性无关组协议（例如在（3-1）中构建的协议）作为诱导协议，构建了求解向量组秩和极大线性无关组问题的Input（ε）-Output（1）安全的代理多方计算协议，其中ε=1/|F|-1且|F|表示有限域的阶；（4-2）将安全双方仿射交协议（例如在（3-2）中构建的协议）作为诱导协议，构建了求解线性方程组公共解问题（在保护隐私的情况下计算两个线性方程组的公共解）的Input（ε）-Output（1）安全的代理双方计算协议，其中ε≦1/|F|-1。
　　 （5）研究了一类特殊的代理多方计算问题，即带公共参数的代理多方计算问题。该模型中，代理多方计算的原始参与者之间拥有（或共享）一个公共参数，且此参数对他们之外任何第三方来说都是保密的。作为具体实例，构建了求解向量组秩和极大线性无关组问题的带公共参数的代理多方计算协议和求解线性方程组公共解问题的带公共参数的代理多方计算协议。

目录

文摘

英文文摘

第一章 绪论

1.1 安全多方计算简介

1.2 论文的研究内容

1.3 论文的组织结构

1.4 本章小结

第二章 安全多方计算的研究现状

2.1 安全多方计算的基本概念

2.1.1 安全多方计算的攻击者模式

2.1.2 安全多方计算的安全模式

2.1.3 安全多方计算的网络模式和信道模式

2.1.4 安全多方计算的计算复杂度、通信复杂度和轮复杂度

2.2 安全多方计算的攻击者模型

2.2.1 半诚实(或被动)攻击者模型

2.2.2 恶意(或主动)攻击者模型

2.2.3 隐蔽攻击者模型

2.3 安全多方计算的可行性结果

2.3.1 被动攻击者模型和主动攻击者模型下的门限结果

2.3.2 攻击者结构与被动、主动攻击者模型下的非门限结果

2.3.3 广义攻击者结构与被动-主动混合模式下的可行性结果

2.3.4 隐蔽攻击者模型下的可行性结果

2.4 安全多方计算的常用密码学工具

2.4.1 同态加密体制

2.4.2 健忘传输协议

2.4.3 秘密共享

2.4.4 可交换的确定型加密体制和语义安全的加密体制

2.5 具体问题的安全多方计算研究现状

2.5.1 安全数据比较问题

2.5.2 分布式线性代数问题

2.5.3 安全集合运算相关问题

2.6 本章小结

第三章 全变换半群与安全映射相等判定问题的研究

3.1 数学基础知识介绍

3.2 保E-序变换半群及其性质的研究

3.2.1 有限保E-序变换半群的Green关系

3.2.2 有限保E-序变换半群的正则性

3.3 映射相等问题的全变换半群解的研究

3.3.1 映射相等问题的判定

3.3.2 映射相等问题的全变换半群解

3.4 变换相等问题的解决方案的研究

3.4.1 变换相等问题的健忘传输解

3.4.2 变换相等问题的同态密码解

3.5 本章小结

第四章 几个数据比较问题的对称密码解的分析

4.1 几个数据比较问题的对称密码解的回顾

4.1.1 Li-Wang-Dai-Luo集合包含问题和百万富翁问题对称密码解

4.1.2 Li-Wang-Dai成员判定问题和广义百万富翁问题对称密码解

4.2 Li-Wang-Dai-Luo百万富翁问题对称密码解的分析

4.2.1 百万富翁问题对称密码解的分析

4.2.2 集合包含问题的同态密码解与百万富翁问题

4.3 Li-Wang-Dai广义百万富翁问题对称密码解的分析

4.3.1 广义百万富翁问题对称密码解的分析

4.3.2 广义百万富翁问题同态密码解

4.4 本章小结

第五章 分布式线性代数问题的研究

5.1 协议准备

5.1.1 基于健忘传输的分布式线性代数协议

5.1.2 基于同态加密体制的向量子空间交协议

5.2 两个分布式线性代数问题的解决方案的研究

5.2.1 向量组秩和极大无关组问题多方求解协议

5.2.2 仿射子空间交问题双方求解协议

5.3 本章小结

第六章 代理多方计算问题的研究

6.1 引言

6.2 代理多方计算问题的研究

6.2.1 代理多方计算及其基本模型

6.2.2 向量组秩和极大无关组代理多方计算协议

6.2.3 代理双方计算的基本模型

6.2.4 线性方程组公共解代理双方计算协议

6.3 带公共参数的代理多方计算问题的研究

6.3.1 带公共参数的向量组秩和极大无关组代理多方计算协议

6.3.2 带公共参数的线性方程组公共解代理双方计算协议

6.4 本章小结

第七章 总结与展望

7.1 论文工作总结

7.2 研究展望

7.3 结语

参考文献

致谢

攻读博士期间完成的论文