摘要
随着网络技术的不断发展,以及高性能计算机、网格等为代表的日益强大的计算环境的出现,极大地改变了计算的含义及计算的方式,这使得用户可以通过网络使用这些强大的计算资源完成自己的计算任务。而在这种环境中,保证用户数据的安全,是计算的基本要求。安全多方计算(Secure Multi-party Computation)正是在这样的背景之下日益引起人们的关注。
安全多方计算问题最早由A.C.Yao提出,描述如下:有n个参与者P_1,P_2,…,P_n,每个参与者拥有一个输入x_1,x_2,…,x_n,要以一种安全的方式共同计算一个函数f(x_1,x_2,…,x_n)。这里的安全是指输出结果的正确性与输入信息、输出信息的保密性,即计算结束之后各参与方只能得到正确的f(x_1,x_2,…,x_n)的值,而不能了解其他方的其他任何信息。
安全多方计算是电子选举、电子拍卖、门限签名等许多应用得以实现的密码学基础。安全多方计算协议牵涉到众多的底层密码协议,目前提出的方案使用到了秘密共享、公钥和私钥加密、同态加密以及不经意传输等诸多常用的安全协议和算法。由于安全多方计算理论对于网络协议的安全具有重要的指导作用,仍然有很多研究人员投入到这个领域来,并且已经取得了丰硕的成果。目前安全多方计算的研究领域包括保护私有信息科学计算问题,保护私有信息计算几何问题,保密数据挖掘问题,安全多方统计分析问题等。
本文的主要成果如下:
1、对SMC的理论、技术与研究现状进行了系统总结,提出了安全多方多数据排序问题,并将前面的技术应用于解决安全多方多数据排序的问题。为安全多方多数据排序问题提出了一个模型,该模型涉及到了安全多方多数据排序问题的各个方面。
2、提出了一个用RSA密码体制和不经意传输来解决安全多方多数据排序问题的解决方案。该方案与多次使用YAO的协议相比,在安全性和公平性上都有很大提高。
3、提出了一个基于大数分解困难性的解决安全多方多数据排序问题的解决方案,该方案可以保证安全性、公平性,同时该方案不需使用任何的加密算法,效率很高。
Along with the continuous development of network technique, and with the appearance of high quality computer and net grid, the meanings and mode of computations are mostly changed. All of this makes it easy that the users can make use of the powerful computation resources. In such circumstance, The safety of users' data become very important and necessary's secure Multi-Party Computation comes forth. Secure Multi-Party Computation was Firstly brought forward by A.C.Yao in 1982: There are n participants P_1,P_2,...,P_n, who want safely compute a function together. And the word safe means that the correctness of output message and the secrecy of input and output message. Concretely, each participant P_i has his secret input message x_i, and all the n participants compute a function together: f(x_1,x_2,...,x_n), when computation has been finished, each P_i knows only value of f(x_1, x_2,...,x_n) ,but not other information.
Secure Multi-Party Computation protocol is an important area in cryptography. It's the basis of many distributed cryptographic protocols, such as threshold cryptosystem, electronic voting and electronic auction etc. It is based on many basic cryptographic protocols (e.g.homomorphic encryption and zeroknownedge proof) and some basic protocols in distributed computation (e.g. obvious transfer and broadcast protocol).Research in the SMC area has been focusing on privacy-preserving scientific computations, privacy-preserving geometric computations, privacy-preserving data mining, privacy-preserving statistical analysis etc.
To sum up, the innovations of this thesis could be summarized as following:
1、We summarize theory、techinique and actuality of SMC,and propose SMMR(Secure Multi-party multi-data Ranking)problem.We give a model about SMMR problem to describe it.
2、We propose a protocol based on RSA homomorphic encryption and OT protocol to solve SMMR problem. This protocol satisfy security and fairness comparing using Yao's protocol repeatedly.
3、We propose a protocol based on large number factorization to solve SMMR problem. This protocol not only satisfy security and fairness, but also don't use any encryption, it has better efficiency.
引文
[1]Shannon C E.Communication theory of secrecy systems,Bell System Technical Journal,28,pp.656-715,1949.
[2]Diffie W,Hellman M E.New directions in cryptography,IEEE Transactions on Information Theory,22(6),pp.644-654,1976.
[3]W.Stallings.Cryptography and Network Security.Second Edition.Prentice Hall,New Jersey,1998.
[4]A.C.Yao.Protocols for secure computations.In Proceedings of FOCS'82,pp.160-164,Chicago,1982.IEEE.
[5]O.Goldreich,S.Micali,and A.Wigderson.How to play any mental game.In Proceedings of the 19th Annual ACM Symposium on Theory of Computing,pp.218-229,1987.
[6]D.Chaum,C.Crepeau,and I.Damgard.Multiparty Unconditionally Secure Protocols.In Proc.20th Annual Symp.On the Theory of Computing,pp.11-19.ACM,1988.
[7]S.Goldwasser and L.Levin,Fair Computation of General Functions in Presence of Immoral Majority,CRYPTO,1990.
[8]O.Goldreich,S.Goldwasser,and N.Linial,Fault-Tolerant Computation in the Full Information Model,32nd FOCS,1991,pp.447-457.
[9]R.Ostrovsky and M.Yung,How to withstand mobile virus attacks,Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing,pp 51-59,1991.
[10]S.Micali and P.Rogaway,Secure Computation,CRYPTO'91,1991.
[11]D.Beaver.Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority.Journal of Cryptology,pp.75-122,1991.
[12]R.Cannetti.Security and composition of multiparty cryptographic protocols.Journal of Cryptology,13(1):143 -202,2000.
[13]M.Be n-Or,S.Goldwasser,and A.Wigderson.Completeness theorems for noncry-ptographic fault-tolerant distributed computations.In 20th STOC,pages 1-10.ACM.1988
[14]D.Chaum,C.Crepeau,and I.Damgard.Multiparty unconditionally secure protocols.In 20~(th) STOC pages1 1-19,1988
[15]S.Micali and P.Rogaway.Secure computation.In CRYPTO'91,1991.
[16]D.Beaver.Foundations of secure interactive computing.In CRYPTO'91,1991.
[17]Matthew Franklin and Moti Yung.Communication complexity of secure computation(extended abstract).In 24~(th) STOC pages 699-710,1992.
[18]Rosario Gennaro,Michael Rabin,and Tal Rabin.Simplified VSS and fast-track Multiparty computations with applications to threshold Cryptography.In Procee-dings of the 1998 ACM Symposium on Principles of Distributed Computing,pages 101-111,1998。
[19]Martin Hirt,Ueli Maurer,and Bartosz Przydatek.Efficient secure multi-party computation.Lecture Notes in Computer Science,1976:143-147,2000.
[20]R.Cramer,I.Damgard,and S.Dziembowski.On the complexity of verifiable secret sharing and multi-party computation.In 32~(nd) STOC May2000.
[21]Ronald Cramer and Ivan Damgard.Zero-knowledge proofs for finite field arithmetic,or:Can zero-knowledge be for free? Lecture Notes in Computer Science,1462:424-428,1998
[22]Michael Harkavy,J.D.Tygar,and Hiroaki Kikuchi.Electronic auctions with private bids.In 3~(rd) USENIX Workshop on Electronic Commerce,pages 61-74,September 1998.
[23]Kikuchi,Hakavy,and Tygar.Multi-round anonymous auction protocols TIEICE:IEICE Transactions on Communications/Electronics/Infrmation and Systems,1999.
[24]Frank Stajano and Ross J.Anderson.The cocaine auction protocol:On the power of anonymous broadcast.In Information Hiding,pages 434-447,1999.
[25]Nakanishi,Watanabe,and Fujiwara.Anonymous auction protocol using undeniable signature.In The 1995 Symposium on Cryptography and Information Security,1995.
[26]M.K.F rankling and M.K.Reiter.The design and implementation of a secure auction service.IEEE Trans.on Software Engineering,22(5):302-312,1996
[27]Mlilgrom.Auctions and bidding:a primer.Journal of Economic Perspectives,pages 3-22,1989.
[28]K.Sako.Universal verifiable auction protocol which hides losing bids.In Procee ding of SCIS'99,pages 35-39,1999.
[29]Rosario Gennaro,Stanislaw Jarecki,Hugo Krawczyk,and Tal Rabin.Robust Threshold DSS signatures.In Theory and Application of Cryptographic Techniques,pages 354-371,1996.
[30]Alfredo De Santis,Yvo Desmedt,Yair Frankel,and Moti Yung.How to share a function securely.In in 2 6~(th) A nnual Symposium on Theory of Computing,pages 522-533.ACM Press,1994.
[31]Yair Frankel,Peter Gemmell,and Moti Yung.Witness-based cryptographic program checking and robust function sharing.In 28~(th) STOC pages 499-508,1996.
[32]Rosario Gennaro,Tal Rabin,Stanislav Jarecki,and Hugo Krawczyk.Robust and efficient sharing of RSA functions.Journal of Cryptology:the journal of the Int ernational Association for Cryptologic Research,13(2):273-300,2000.
[33]D.Chaum.Untraceable electronic mail,returen addresses,and digital Pseudonyms.Communications of the ACM,24(2):84-88,1981.
[34]Markuss Jakobsson and Ari Juels.Millimix:Mixing in small batches.Technical Report 99-33,DIMACS,10,1999.
[35]Markus Jakobsson and Ari Juels.Mix and match:Secure function evaluation viaciphertexts.Lecture Notesin Computer Science,1976:162-166,2000.
[36]M.Abe.Mix-networks on permutation networks.In ASIACRYPT'99,pages258-273.1999.
[37]A.Yao.Protocol for Secure Computations[C].In Proceeding of 23rd IEEE Symposium on Foundations of Computer Science.Los Alamitos,CA:IEEE Computer Society Press,1982:160-164.
[38]Wenliang Du,Yunghsiang S.Han and Shigang Chen.Privacy-Preserving Multivariate Statistical Analysis:Linear Regression and Classification//Proceedings of the 4th SIAM International Conference on Data Mining.Lake Buena Vista,Florida,2004:222-233.
[39]A.Shamir.How to share a secert.Communication of the ACM,22(11):612-613,1979.
[40]G.R.Blakley.Safe guarding cryptographic keys Conference.vo.148,Montvale,N J:A FIPSP ress.In Porceedings of the National Computer,pp.313-317,1979.
[41]T.Rabin and M.Ben-Or.Verifiable secret sharing and multiparty protocols with honest majority.In Proc.21~(st) ACM Symposium on the Theory of Computing (STOC).pp.73-85.1989.
[42]D.beaver.Secure multiparty protocols and zero-knowledge proff system tolerating a faulty minority.Journal of Cryptology 4(2);75-122.1991.
[43]S.Even,O.Goldreich and A.Lempel,A random protocol for sign contracts,communication of the ACM28,1985,pp.218-229.
[44]S.Wiesner,Conjugate Coding,SIGACT Newsl5,pp.78-88,1983.
[45]GBrassard,C.crepeau and J.M.Robert,All or Nothing Disclosure of Secrets,Advance in cryptology crypto'86,LNC263,springerverlag,pp.234-238,1987.
[46]Cachin C.Efficient private bidding and auctions with an oblivious third party.Proc of the 6th ACM Conf on Computer and Communications Security.Assn for Computing Machinery,1999.120-127.
[47]刘文,罗守山,陈萍;利用ElGamal密码体制解决安全多方多数据排序问题[J];通信学报;Vol.28(11):1-5,Nov.2007.
[48]李顺东,张选平,排序问题的多方保密协议[J];西安交通大学学报;Vol.42(2):231-233,Feb.2008.
[49]秦静,张振峰,冯登国,李宝;一个特殊的安全双方计算协议[J];通信学报;2004年11期;39-46.
[50]李顺东,戴一奇,游启友,姚氏百万富翁问题的高效解决方案,电子学报,Vol.33(5):769-773,2005.
[51]秦波,秦慧,周克复,王晓峰,王育民;常数复杂性的百万富翁协议,西安理工大学学报,(2005)vol.21 No.2.
[52]Jakobsson M,Yung M.Proving without knowing:on oblivious,agnostic and blindfolded provers[J].Crypto 1996.Lee-ture Notes in Computer Science,1996.1109:186-200.
[53]boudot F,Schoenmakers B,Traor6 J.A fair and efficient solution to the socialist millionaires'Problem[J].Discrete Applied Mathematics,Special Issue on Coding and Cryptography.Elsevier,2000.
[54]Fischlin M.A cost-effective pay-per-multiplication comparison method for millionaires[A].RSA Security 2001 Cryptographer's Track,Lecture Notes in Computer Science,2001,2020:457-471.
[55]O Goldreich.Secure Multi-party Computation(working draft)[EB/OL].http://www.wisdom.weizmann.ac.il/-oded/pp.html,2000-10.
[56]Du,W.L.and Atallah,M.J.:Privacy-preserving cooperative scientific computations.Proceedings of the 14th IEEE Computer Security Workshop.(2001)273-282.
[57]Mikhail J Atallah,Wenliang Du.Secure multi-party computational geometry.In:Lecture Notes in Computer Science 2125,Berlin:Springer,2001:165-179.
[58]Lindell,Y.and Pinkas,B.:Privacy preserving data mining.Advances in Cryptology-Crypto2000,Lecture Notes in Computer Science,1880.(2000)36-44.
[59]Du,W.L.and Atallah,M.J.:Privacy-preserving statistical analysis.Proceedings of the 17th Annual Computer Security Applications Conference,pages.(2001)102-110.
[60]R.Agrawal,A.Evfimievski,R.Srikant.Information Sharing across Private Databases[C].In Proceedings of the 2003 ACM SIGMOD international conference on Management of Data.ACM Press,2003:86-97.
[61]M Rabin.How to exchange secrets by oblivious transfer[R].Technical Report TR-81,Aiken Computation klbDIatofy,Harvard Univ,1981.
[62]Yi Mu,Junqi Zhang,Vijay Varadharajan,m out ofn oblivious transfer,ACISP 2002,Lecture Notes in Computer Science 2384,Springer Verlag,2002.pp.395-405.
[63]Wen-Guey Tzeng:Efficient 1-Out-of-n Oblivious Transfer Schemes with Universally Usable Parameters.IEEE Trans.Computers 53(2):232-240(2004)