【作者】 郑强；

【导师】 罗守山；

【作者基本信息】 北京邮电大学 ， 信息安全， 2010， 博士

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

【Abstract】 Generally speaking, a secure multi-party computation (SMC) refers to the problem where two or more parties want to jointly compute a function based on their private inputs in a distributed network, and that no more information is revealed to a participant in the computation than can be inferred form that participant’s input and output. Secure multi-party computation was firstly brought forward by A.C.Yao in 1982. after five years, Goldreich、Micali and Wigderson presented the secure multi-party computation protocol with cryptography security, which can securely compute an arbitrary function. With the internet development and popularization, it is a important research direction using SMC to solve several special practical fields, such as computational geometry, data mining, set elements, algebra problems and electronic voting. Using the general solution for special cases of multi-party computation can be impractical. In 1998, O.Goldreich pointed out that, special solutions should be developed to solve some special problems.The main research content of this dissertation is as follows, 1. The theory, technique and actuality of Millionaire’s problem and Millionaire’s extended problem were summarized, including research on Millionaire’s problem in the cryptographic communication model and in information theoretic communication model.2. The theory, technique and actuality of algebra problems were summarized, including rank of matrix, solution of algebra equation etc, which adversary model includes semi honest, malicious and covert and communication model includes cryptography and information theory.3. The theory, technique and actuality of privacy preserving set operate protocols were summarized, including privacy preserving set intersection protocol, privacy preserving set pattern matching protocol etc, which adversary model includes semi honest, malicious and covert and communication model includes cryptography and information theory.Correspondingly, the main contributions of this dissertation are as follows:1. We present the extended Millionaires’problem in the information theoretic communication model, which is not only efficient but considering the case of the equality of two numbers.2. We present algebra computation protocol in the semi honest attack model, such as multi-party matrices addition protocol, extended multi-party matrices product protocol and multi-party matrices division protocol etc. using jointed secret randomness technique and secure inversion of field matrices technique, we also present SMC of determinant, SMC of rank and SMC for determining similarity between matrices in the information theoretic model.3. We present whether multi-party sets are jointed, privacy preserving set pattern matching protocol, privacy preserving set intersection cardinality protocol, privacy preserving ser difference protocol and privacy preserving frequency highest element in set-intersection protocol which can against a semi honest adversary in the cryptographic model. We also present privacy preserving set difference protocol and privacy preserving set intersection cardinality protocol which can against a semi honest adversary, privacy preserving set difference and privacy preserving set pattern matching protocol which can against a malicious adversary in the information theoretic model.更多还原