摘要
安全多方计算(Secure Multi-party Computation,简称SMC)是指在一个互不信任的多用户的网络中,拥有秘密输入的两方或者多方,希望利用各自的秘密输入共同计算出一个函数。并且保证在计算完成后,每个参与方都能接收到正确的输出,每个参与方只能知道自己的输入和输出,而不知道其他参与方的输入和输出。安全多方计算问题最早来源于图灵奖得主A.C.Yao于上世纪的80年代初提出的安全两方计算,5年以后,Goldreich、Micali和Wigderson提出了可以计算任意函数的基于密码学安全的安全多方计算协议。随着Internet的发展和普及,如何利用安全多方计算来解决某些特定的实际问题是一个重要的研究方向,例如将多方安全计算引入到计算几何,数据挖掘,集合元素,代数问题和电子选票等.如果用通用的协议来解决这些特殊的实例是不高效的,所以在1998年,O.GoldRiech指出了对于解决一些特殊的问题,需要设计一些特殊的协议才能够高效的解决这些特殊实例.
本文的研究内容主要包括以下的几个方面:
1.总结了安全多方计算中百万富翁问题及其百万富翁扩展问题研究现状和现有研究方案,包括密码学通信模型下和信息论通信模型下对于百万富翁的问题进行研究。
2.总结了安全多方计算中的代数问题的研究现状和现有的研究方案,在密码学通信模型下和信息论通信模型下,将分别从半诚实攻击者模型,恶意攻击者模型和隐蔽攻击者模型中,对于主要研究的代数问题例如矩阵的基本运算以及矩阵的秩,代数等式的求解和相似性判定等等进行研究。
3.总结了安全多方计算中的隐私保护的集合运算协议的研究现状和研究方案,在密码学通信模型下和信息论通信模型下,将分别从半诚实攻击者模型,恶意攻击者模型和隐蔽攻击者模型中,对于主要研究的隐私保护的集合运算协议例如隐私保护的集合交集,隐私保护的集合模式匹配等等进行研究。
与之对应,本文取得了一些研究成果,主要包括:
1.提出了信息论模型下的百万富翁协议的扩展协议,此协议不仅是高效的,还考虑到了两个数相等的情况。
2.提出了一些半诚实模型下的代数运算协议,例如多方矩阵的加法协议,多方矩阵乘积的扩展协议和多方矩阵的除法协议等。并且利用联合秘密随机数的产生技术,域矩阵的安全求逆的技术和无界扇入乘法技术,在信息论模型下提出了多维矩阵乘积的行列式协议,求矩阵秩的协议和判定两个矩阵是否相似协议。
3.在密码学的通信模型下,给出了半诚实攻击者模型下的判定多方集合是否相交的协议,隐私保护的集合模式匹配协议,隐私保护的集合交集基数的协议,隐私保护的集合差集协议和隐私保护的集合中出现频率最高的元素。在信息论的通信模型下,给出了半诚实攻击者模型下的隐私保护的集合交集协议,隐私保护的集合模式匹配协议,隐私保护的集合差集协议和隐私保护的集合交集的基数协议等。在恶意攻击者模型下给出了隐私保护的集合模式匹配协议和隐私保护的集合差集协议等。
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.
引文
[I]Atul K.信息安全原理.邱仲潘等译,北京:清华大学出版社,2005
[2]Michael W E, Herbert M J.信息安全原理.徐焱译,北京:清华大学出版社,2003
[3]冯登国.国内外信息安全研究现状及其发展趋势.网络安全技术与应用,2001
[4]Shannon C E. Communication theory of secrecy systems, Bell System Technical Journal,28,1949,656-715
[5]Diffie W, Hellman M E. New directions in cryptography,IEEE Transactions on Information Theory,22(6),1976,644-654
[6]Rabin M O, How to Exchange Secrets by Oblivious Transfer, Tech. Memo TR81,Aiken Computation Laboratory, Harvard U.,1981
[7]Even S, Goldreich O and Lempel A, A Randomized Protocol for Signing Contracts, CACM,28(6) 1985,637-647
[8]Chor B, GoldWasser S and Micali S et al., Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults, In 26th IEEE Symposium on Foundations of Computer,1985,383-395
[9]Shamir A, How to Share a Secret, CACM, vol.22,1979,612-613
[10]Yao A C. Protocols for secure computations. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. USA, Washington:IEEE computer society,1982,160-164.
[11]Goldreich O, Micali S, and Wigderson A. How to play any mental game. In proceedings of the 19th annual ACM symposium on theory of computing.1987, 218-229
[12]Chaum D, Crepeau C, and Damgard I. Multiparty unconditionally secure protocols. In proceedings of the twentieth annual ACM symposium on theory of computing. USA, New York:ACM,1988,11-19.
[13]Goldwasser S and Levin L. Fair computation of general functions in presence of immoral majority. In proceedings of the 10th annual international cryptology conference on advances in cryptology. UK, London:Springer-Verlag, 1990,77-93
[14]Goldreich 0, Goldwasser S, and Linial N. Fault-tolerant computation in the full information model. In proceedings of the 32nd annual symposium on foundations of computer science. USA, Washington:IEEE computer society,1991, 447-457
[15]Ostrovsky R and Yung M. How to withstand mobile virus attacks, In proceedings of the 10th annual ACM symposium on principles of distributed computing.1991,51-59.
[16]Micali S and Rogaway P. Secure Computation. CRYPTO'91.1991
[17]Beaver D.Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority. Journal of Cryptology.1991,75-122.
[18]Cannetti R. Security and composition of multiparty cryptographic protocols. Journal of Cryptology.13(1),2000:143-202.
[19]Be n-Or M, Goldwasser S,and Wigderson A. Completeness theorems for noncry-ptographic fault-tolerant distributed computations. In proceedings of the twentieth annual ACM symposium on theory of computing. USA, New York:ACM, 1988,1-10.
[20]Chaum D, Crepeau C, and Damgard I. Multiparty unconditionally secure protocols. In proceedings of the twentieth annual ACM symposium on theory of computing. USA, New York:ACM,1988,11-19.
[21]Beaver D.Foundations of secure interactive computing. In CRYPTO'91. UK, London:Sprongger-Verlag,1991,377-391.
[22]Franklin M and Yung M. Communication complexity of secure computation(extended abstract). In 24th STOC.1992,699-710.
[23]Gennaro R, Rabin M, and Rabin T. Simplified VSS and fast-track multiparty computations with applications to threshold cryptography.In proceedings of the 1998 ACM symposium on principles of distributed computing.1998,101-111.
[24]Hirt M, Maurer U, and Przydatek B. Efficient secure multi-party computation. In Advances in cryptology-ASIACRYPT 2000. Lecture Notes in Computer Science,2000,143-161.
[25]Cramer R, Damgard I, and Dziembowski S. On the complexity of verifiable secret sharing and multi-party computation. In proceedings of the thirty-second annual ACM symposium on theory of computing. USA, New York: ACM,2000,325-334.
[26]Cramer R and Damgard I. Zero-knowledge proofs for finite field arithmetic,or:Can zero-knowledge be for free? Advances in Cryptology-CRYPTO '98. Lecture Notes in Computer Science,1998,424-441.
[27]Harkavy M, Tygar J D,and Kikuchi H. Electronic auctions with private bids.In 3rd USENIX workshop on electronic commerce,1998,61-74.
[28]Kikuchi H and Tygar. Multi-round anonymous auction protocols TIEICE: IEICE transactions on communications/electronics/information and Systems,1999.
[29]Stajano F and Anderson R J. The cocaine auction protocol:On the power of anonymous broadcast. In proceedings of the third international workshop on information hiding. UK, London:Springer-Verlag,1999,434-447.
[30]Nakanishi, Watanabe and Fujiwara. Anonymous auction protocol using undeniable signature. In the 1995 symposium on cryptography and information security,1995.
[31]Frankling M K and Reiter M K. The design and implementation of a secure auction service. IEEE Trans. on Software Engineering.22(5),1996:302-312,
[32]Mlilgrom. Auctions and bidding:a primer. Journal of economic perspectives,1989,3-22.
[33]Sako K. Universal verifiable auction protocol which hides losing bids.In proceeding of SCIS'99,1999,35-39.
[34]Gennaro R, Jarecki S, Krawczyk H,et al. Robust threshold DSS signatures, In theory and application of cryptographic techniques,1996,354-371.
[35]Santis AD, Desmedt Y, Frankel Y,et al. How to share a function securely, In 26th annual symposium on theory of computing. ACM Press,1994,522-533.
[36]Frankel Y, Gemmell P, and Yung M. Witness-based cryptographic program checking and robust function sharing. In 28th STOC.1996,499-508.
[37]Gennaro R, Rabin T, Jarecki S, et al. Robust and efficient sharing of RSA functions. Journal of cryptology:the journal of the international association for cryptology research.13 (2),2000:273-300.
[38]Chaum D. Untraceable electronic mail, return addresses, and digital Pseudonyms. Communications of the ACM,24(2),1981,84-88.
[39]Jakobsson M and Juels A. Millimix:mixing in small batches. Technical Report DIMACS,10,1999,99-33.
[40]Jakobsson M and Juels A. Mix and match:secure function evaluation via ciphertexts. Lecture Notes in Computer Science,2000,162-177.
[41]Abe M. Mix-networks on permutation networks. In ASIACRYPTO'99, 1999,258-273.
[42]Blum M, Coin Flipping by Phone, IEEE Spring COMPCOM, February 1982:133-137.
[43]Naor M, Bit Commitment Using Pseudorandom Generators, Journal of Cryptology, vol.4,1991:151-158.
[44]Goldreich 0, Foundation of Cryptography-Fragments of a Book, February,1995, Available from http://www.weizmann.ac.il/~oded/foc-book.html.
[45]Goldwasser S, Micali S and Rockoff C, The Knowledge Complexity of Interactive Proof Systems, SIAM journal on Computer Science, vol.18,1989: 186-208.
[46]Bellare M and Goldreich 0, On Defining Proofs of Knowledge, In Crypto92, Springer-Verlag LNCS, vol.740:390-420.
[47]李强,颜浩,陈克非,安全多方计算协议的研究与应用,计算机科学,30(2)2003,52-55
[48]Gennaro R. Rah in M, Rabin T. Simplified VSS and fast-track multiparty computations with applications to threshold cryptography. In:Proc.of the 1998 ACM Symposium on Principles of Distributed Computing
[49]Matthew T, Franklin T and Habert S. Joint encryption and message efficient secure computation. Journal of Cryptology,1996,9(4):217-232
[50]Paillier P. Public-key cryptosystems based on composite degree residue classes. In:Michael Wiener, ed. Advances in Cryptology-EuroCrypt'99, Berlin, 1999.223-238
[51]Goldreich O. The Foundations of Cryptography-Volume 1, Basic Tools, Cambridge University Press 2001.
[52]Goldreich O. The Foundations of Cryptography-Volume 2, Basic Tools, Cambridge University Press 2004.
[53]罗文俊,安全多方计算理论及其应用,博士论文,1995
[54]Aumann Y.and Lindell Y.:Security against covert adversaries:Efficient protocols for realistic adversaries. In:Vadhan, S.P. (ed.) TCC 2007. LNCS, vol.4392, 2007
[55]Vipul G, Payman M and Adam S.Efficient Two Party and Multiparty Computation Against Covert Adversaries. EUROCRYPT2008, LNCS,2008,289-306
[56]Hirt, M., Maurer, U., Przydatek, B. Efficient secure multi-party computation[C]//Advances in Cryptology-ASIACRYPT'00. LNCS, Vol.1976. 2000:143-161
[57]Kilian J. Founding cryptography on oblivious transfer. In Proceedings of 20th ACM Symposium on Theory of Computing.1988 20-31.
[58]Chu C W. Tzeng G. Efficient k-out-of-n transfer schemes with adaptive and non adaptive queriers. PKC2005,172-183.
[58]Lour S and Lipamaa H. On security of sublinear oblivious transfer. Cryptology eprint Archive,2006
[59]Ogata W, Kurosawa K. Oblivious keyword search. Journal of complexity, 20(2),2006,356-371.
[60]Blakley G R. Safe guarding cryptographic keys. In national computer conference. New York, USA,1979,313-317.
[61]Brassard Q Crepeau C. Information Theoretic Reduction among Disclosure problems. In Proceedings of 27th IEEE Symp. Foundations of Computer Science,1986,168-173
[62]Brassard G, Crepeau C Oblivious transfer and intersecting codes. IEEE Trans Information Theoretic 42(6) 1996,1769-1780
[63]Naor M and Pinkas B. Oblivious Transfer and Polynomial Evaluation. In Proceeding of 31st ACM Symp. Theory of Computing,1999,245-254
[64]Naor M and Pinkas B. Efficient oblivious Transfer Protocol. In Proc.12st Symp.Discrete Algorithms,2001.448-457
[65]Stem J P. A new and efficient All-or-Nothing disclosure of Secrets Protocols. In Proc. Advances in Cryptology,1998.357-371.
[66]Blakley G R. Safe guarding cryptographic keys. In national computer conference. New York, USA,1979,313-317.
[67]Asmuth and Bloom.A modular approach to key safeguarding. IEEE Transactions on information Theory.1983,208-210.
[68]Hellman M E, Karnin E D and Greene J W. On sharing secret systems. IEEE Transactions on Information Theory,1983,35-41.
[69]Benaloh J and Leichter J. Generalized secret sharing and monotone functions. Lecture Notes in Computer Science,1990,27-35.
[70]Saito A, Ito M and Nishizeki T. Multiple assignment scheme for sharing secret. Journal of Cryptology,6(1),1993.
[71]El Gamal T. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transaction on Information Theory.31(4),1985:469-472
[72]Paillier P. Public-key crytosystems based on composite degree residue classes. Advance in cryptology-EuroCrypy'99. Berlin:LNCS,1999,223-238.
[73]Atallah M J and Du W. Secure Multiparty Computational Geometry. In LNCS, WADS 2001,165-179.
[74]Du W and Atallah M J. Secure multiparty Computation Problems and their Applications:A Review and Open Problems. In New Security Paradigm Workshop, 2001. Cloudcroft, US A.2001,11-20
[75]Ioannidis.I and Grama A. A secure protocol for computing dot-products in clustered and distributed environments. In the 2002 International Conference on Parallel Processing,2002.379-384.
[76]Clifton C and Kantarcioglu M, et al. Tools for Privacy Preserving Distributed Data Mining. In SIGKDD Explorations.2002.28-34.
[77]Shen C, Zhan J. et al, Information theoretically secure number-product protocol. In Proceedings of the Sixth International Conference on Machine Learning and Cyberbetics, Hong Kong,2007,19-22
[78]Dragos T and Sanguthevar R. Fast cryptographic multiparty protocols for computing Boolean scalar products with applications to privacy-preserving association rule mining in vertically partitioned data. LNCS, DaWak 2007, 2007,418-427
[79]Cheung S, and Thinh N. Secure multiparty computation between distrusted networks terminals. Eurasip. Journal on Information security,2007,1-11
[80]李顺东,戴一奇,游启友.姚氏百万富翁问题的高效解决方案.电子学报.33(5),2005:769-773.
[81]秦波,秦慧,王育民等。常数复杂性的百万富翁协议,西安理工大学学报,2005,149-153
[82]Shundong L,Daoshun W. Yiqi D. Symmetric cryptographic solution to Yao's millionaires'problem and an evaluation of secure multiparty computations. Information,2008,244-255
[83]Takashi N, Kazuo O, Multiparty computation for interval, equality, and comparison without bit-decomposition protocol. PKC 2007, LNCS,2007,343-360
[84]Damgard I, Fitzi. M,Kiltz.E, Unconditionally secure constant-rounds multiparty computation for equality, comparison, bits and exponentiation, TCC 2006, LNCS,2006,285-304
[85]J. Bar-Ilan, D. Beaver:Non-cryptographic fault-tolerant computing in constant number of rounds of interaction, Proc. ACM PODC'89,1989,201-209
[86]秦静,张振峰,冯登国,一种特殊的安全两方计算协议,通信学报,25(11),2004
[87]Boudot F, Schoenmakers B, Traore J. A fair and efficient solution to the socialist millionaires' problem. Discrete Applied Mathematics.2001:23-36.
[88]Tuan J, Ye Q, Wang H.X, Secure computation of vector dominance problem, LNCS, ISPEC 2008,2008,319-333
[89]Atallah M. J and Du W. L Secure multi-party computation geometry. LNCS. WADS 2001,2001,165-179
[90]Sang Y.P, Shen H, Zhang Z.H, An efficient protocol for the problem of secure two-party vector dominance.
[91]赵洋,蓝天,马新新。基于加同态公钥密码体制的两方安全议价协议,计算机研究与发展,2006
[92]赵洋,蓝天,马新新。一种改进的两方安全议价协议,电子科技大学学报,2007,
[93]石伟敏,彭长根,一种改进的无可信第三方的两方安全议价协议,贵州大学学报,2009
[94]Ivan D, Martin G, and Mikkel K Homomorphic encryption and secure comparison. Appiled Cryptography,1(1),2008,22-32.
[95]陈晓峰,张方国。一种改进的密封式标价电子拍卖协议,电子与信息学报,21(7),2002
[96]肖清华,陈小平,潘雪增,一种推广的power安全拍卖方案,浙江大学学报(工学版)39(2),2005,221-224
[98]Payman M, Enay W. Efficient secure linear algebra n the presence of covert or computationally unbounded adversaries. CRYPTO2008, LNCS,2008,481-496
[99]Nissim K, Enav W. Communication efficient secure linear algebra. TCC 2006,LNCS,2006,522-541
[100]Cramer R, Kiltz E, Padro C, A note on secure computation of the Moore-penrose pseudo-inverse and its application to secure linear algebra.. CRYPTO 2007, LNCS,2007
[101]Cramer R, Damgaard I. Secure distributed linear algebra in a constant number of rounds, CRYPTO 2001, LNCS,2001,119-136
[102]罗文俊,安全多方计算的理论及其应用,2005,博士论文
[103]王小妹,安全多方计算的协议研究,2008,硕士论文。
[104]Cramer R, Damgaard I. General secure multi-party computation from any linear secret sharing scheme.1-19
[105]Kisyias A, Mitrofanova A. Testing disjointness of private datasets, LNCS,2005,109-124
[106]Hohenberger,S., Weis,S.A.:Honest-verifier private disjointness testing without random oracle. PET 2006, LANS,2006,277-294
[107]Ye, Q.S., Wang, H.X., Pieprzyk,J,.et al.:Efficient disjointness tests for private datasets, ACISP 2008, LNCS 5107,2008,155-169
[108]Frikken. K:Privacy-preserving set union, ACNS 2007, LNCS 4521, 237-252,2007
[109]Brivkel. J and Shmatikov. V:Privacy-preserving graph algorithms in the semi-honest model. ASIACRYPT 05, LNCS 3788,2005,236-252
[110]Kantarcioglu. M and Clifton. C. Privacy-preserving distributed mining of association rules on horizontally partitioned data, IEEE Transactions on Knowledge and Data Engineering,16(9):1026-1037,2004
[111]Kissner. L and Song. D:Privacy-preserving set operations. CRYPTO 05, LNCS 3621,2005
[112]Segre. A. M, and Wildenberg. A:Privacy-preserving data set union, Proc of the 2006 Conference on privacy in Statistical Databases,2006
[113]Yingpeng. S, Hong S.. An Efficient and secure protocol for privacy preserving set intersection,1-18
[114]Yingpeng. S, Hong S..:Efficient protocols for privacy preserving matching against distributed datasets, ICICS 2006,210-227
[115]Freedman M. J, Nissim K and Pinkas B:Efficient private matching and set intersection, EUROCYPTO'04, LNCS 3027,2004,1-19
[116]Sang Y. P and Shen H:Privacy-preserving set intersection based on bilinear group. ACSC 2008,47-54
[117]Li R. H and Wu C. K:An Unconditionally secure protocol for multiparty set intersection. ANCS 2007, LNCS 4521,2007,226-236.
[118]Vaidya J and Clifton C,:Secure set intersection cardinality with application to association rule mining, Journal of Computer Security,2005,593-622
[119]Hazay C and Yehuda L.:Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries. TCC'2008, LNCS 4948,2008,155-175
[120]Yindle Q.S.:Privacy-preserving distributed set intersection, ARE'08. 2008,1332-1339