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