论文部分内容阅读
安全多方计算(Secure Multi-party Computation,简称SMC)是指在一个互不信任的多用户的网络中,拥有秘密输入的两方或者多方,希望利用各自的秘密输入共同计算出一个函数。并且保证在计算完成后,每个参与方都能接收到正确的输出,每个参与方只能知道自己的输入和输出,而不知道其他参与方的输入和输出。安全多方计算问题最早来源于图灵奖得主A.C.Yao于上世纪的80年代初提出的安全两方计算,5年以后,Goldreich、Micali和Wigderson提出了可以计算任意函数的基于密码学安全的安全多方计算协议。随着Internet的发展和普及,如何利用安全多方计算来解决某些特定的实际问题是一个重要的研究方向,例如将多方安全计算引入到计算几何,数据挖掘,集合元素,代数问题和电子选票等.如果用通用的协议来解决这些特殊的实例是不高效的,所以在1998年,O.GoldRiech指出了对于解决一些特殊的问题,需要设计一些特殊的协议才能够高效的解决这些特殊实例.本文的研究内容主要包括以下的几个方面:1.总结了安全多方计算中百万富翁问题及其百万富翁扩展问题研究现状和现有研究方案,包括密码学通信模型下和信息论通信模型下对于百万富翁的问题进行研究。2.总结了安全多方计算中的代数问题的研究现状和现有的研究方案,在密码学通信模型下和信息论通信模型下,将分别从半诚实攻击者模型,恶意攻击者模型和隐蔽攻击者模型中,对于主要研究的代数问题例如矩阵的基本运算以及矩阵的秩,代数等式的求解和相似性判定等等进行研究。3.总结了安全多方计算中的隐私保护的集合运算协议的研究现状和研究方案,在密码学通信模型下和信息论通信模型下,将分别从半诚实攻击者模型,恶意攻击者模型和隐蔽攻击者模型中,对于主要研究的隐私保护的集合运算协议例如隐私保护的集合交集,隐私保护的集合模式匹配等等进行研究。与之对应,本文取得了一些研究成果,主要包括:1.提出了信息论模型下的百万富翁协议的扩展协议,此协议不仅是高效的,还考虑到了两个数相等的情况。2.提出了一些半诚实模型下的代数运算协议,例如多方矩阵的加法协议,多方矩阵乘积的扩展协议和多方矩阵的除法协议等。并且利用联合秘密随机数的产生技术,域矩阵的安全求逆的技术和无界扇入乘法技术,在信息论模型下提出了多维矩阵乘积的行列式协议,求矩阵秩的协议和判定两个矩阵是否相似协议。3.在密码学的通信模型下,给出了半诚实攻击者模型下的判定多方集合是否相交的协议,隐私保护的集合模式匹配协议,隐私保护的集合交集基数的协议,隐私保护的集合差集协议和隐私保护的集合中出现频率最高的元素。在信息论的通信模型下,给出了半诚实攻击者模型下的隐私保护的集合交集协议,隐私保护的集合模式匹配协议,隐私保护的集合差集协议和隐私保护的集合交集的基数协议等。在恶意攻击者模型下给出了隐私保护的集合模式匹配协议和隐私保护的集合差集协议等。