摘要
安全多方计算是近年来密码学的研究热点,本文主要研究保密科学计算中最值(最大值、最小值)问题的安全多方计算,关于该问题现有的解决方案不多,而且目前尚未出现架构在云计算环境下的解决方案.针对此问题,本文首先对保密数据进行0-1编码,使得保密数据隐藏于所编码的0-1数组中,然后利用多密钥NTRU全同态加密算法,分别设计了在云计算环境下解决最大值、最小值问题的协议,并且,在半诚实模型下,利用模拟范例的方法,对本文提出协议的安全性进行了证明.本文分析表明:在性能方面,和以往协议相比,本文提出的的最大值、最小值解决方案,不仅是首次架构在云计算环境下的解决方案,而且该方案还可以抗量子攻击;在效率方面,由于本文构造的协议都架构在云计算平台上,这能为用户节省大量的计算成本,所以本文给出的协议取得了更高的效率.最后,本文将设计的两个新协议应用在统计学领域,解决了一个新问题—多方保密计算极差问题,该方案简洁安全.
Secure multiparty computation becomes a cryptography research hotspot in recent years.This work mainly studies how to compute the maximum and minimum values securely for some privately input numbers. This is a problem of private-preserving scientific computation. However, so far, very few results are known, and there are no solutions designed for the cloud computing environment. Aiming at these issues, we first adopt 0-1 encoding to encode a private number into an array.This coding technique can hide the confidential data in the array encoded with 0-1. The protocols to compute the maximum and the minimum values are designed by using the multikey NTRU fully homomorphic encryption algorithm in cloud environment. The security of the proposed protocols in this study is analyzed in the semi-honest model, the security proof utilizes the method of simulation paradigm. It is the first time to construct secure computation protocols for the maximum and the minimum values in cloud computing environment, and the solutions can also resist quantum attack.The schemes designed in this study have been adapted to the cloud environment, which can save a large amount of computation cost for users. Finally, the proposed protocols are applied to statistics,and a new problem about the secure multiparty computation of range problem is solved. The solution is simple and secure.
引文
[1]YAO A C.Protocols for secure computations[C].In:Proceedings of 23rd IEEE Symposium on Foundations of Computer Science.IEEE,1982:160-164.[DOI:10.1109/sfcs.1982.38]
[2]FREUDIGER J,RANE S,BRITO A E,et al.Privacy preserving data quality assessment for high-fidelity data sharing[C].In:Proceedings of the 2014 ACM Workshop on Information Sharing&Collaborative Security.Scottsdale,AZ,USA,2014:21-29.[DOI:10.1145/2663876.2663885]
[3]AGRAWAL D,AGGARWAL C C.On the design and quantification of privacy preserving data mining algorithms[C].In:Proceedings of the Twentieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems.ACM,2001:247-255.[DOI:10.1145/375551.375602]
[4]LINDELL Y,PINKAS B.Secure multiparty computation for privacy-preserving data mining[J].Journal of Privacy and Confidentiality,2009,1(1):59-98.[DOI:10.29012/jpc.v1i1.566]
[5]ALDEEN Y A,SALLEH M,RAZZAQUE M A.A comprehensive review on privacy preserving data mining[J].SpringerPlus,2015,4(1):694.[DOI:10.1186/s40064-015-1481-x]
[6]AGGARWAL C C.Privacy preserving data mining.In:Data Mining[M].Springer Cham,2015:663-693.[DOI:10.1007/978-3-319-14142-8_20]
[7]LUO Y L,HUANG L S,JING W W,et al.Privacy protection in the relative position determination for two spatial geometric objects[J].Journal of Computer Research and Development,2006,43(3):410-416.罗永龙,黄刘生,荆巍巍,等.空间几何对象相对位置判定中的私有信息保护[J].计算机研究与发展,2006,43(3):410-416.
[8]CHEN Z H,LI S D,HUANG Q,et al.Privacy-preserving determination of spatial location-relation in cloud computing[J].Chinese Journal of Computers,2017,40(2):351-363.[DOI:10.11897/SP.J.1016.2017.00351]陈振华,李顺东,黄琼,等.云外包计算中空间位置关系的保密判定[J].计算机学报,2017,40(2):351-363.[DOI:10.11897/SP.J.1016.2017.00351]
[9]ZHU G B,TAN Y W,ZHAO Y,et al.An efficient and secure geometric intersection computation protocol[J].Journal of University of Electronic Science and Technology of China,2014,43(5):781-786.[DOI:10.3969/j.issn.1001-0548.2014.05.026]朱国斌,谭元巍,赵洋,等.高效的安全几何交集计算协议[J].电子科技大学学报,2014,43(5):781-786.[DOI:10.3969/j.issn.1001-0548.2014.05.026]
[10]YANG X L,LI S D,ZUO X J.Secure multi-party geometry computation[J].Journal of Cryptologic Research,2016,3(1):33-41.[DOI:10.13868/j.cnki.jcr.000107]杨晓莉,李顺东,左祥建.计算几何问题的多方保密计算[J].密码学报,2016,3(1):33-41.[DOI:10.13868/j.cnki.jcr.000107]
[11]DU W L,ATALLAH M J.Privacy-preserving cooperative statistical analysis[C].Seventeenth Annual Computer Security Applications Conference.IEEE,2001:102-110.[DOI:10.1109/ACSAC.2001.991526]
[12]DU W L,ATALLAH M J.Privacy-preserving cooperative scientific computations[C].In:Proceedings of 14th IEEE Computer Security Foundations Workshop.IEEE,2001:273-282.[DOI:10.1109/CSFW.2001.930152]
[13]LOFTUS J,SMART N P.Secure outsourced computation[C].In:Progress in Cryptology-AFRICACRYPT 2011.Springer Berlin Heidelberg,2011:1-20.[DOI:10.1007/978-3-642-21969-6_1]
[14]HU X,TANG C M.Securely outsourcing computation of point multiplication on elliptic curves in cloud computing[J].Journal of Hunan University of Science&Technology(Natural Science Edition),2014,29(1):119-123.[DOI:10.13582/j.cnki.1672-9102.2014.01.024]胡杏,唐春明.云环境下安全外包椭圆曲线点的乘法[J].湖南科技大学学报(自然科学版),2014,29(1):119-123.[DOI:10.13582/j.cnki.1672-9102.2014.01.024]
[15]JIANG H,XU Q L.Secure multiparty computation in cloud computing[J].Journal of Computer Research and Development,2016,53(10):2152-2162.[DOI:10.7544/issn1000-1239.2016.20160685]蒋瀚,徐秋亮.基于云计算服务的安全多方计算[J].计算机研究与发展,2016,53(10):2152-2162.[DOI:10.7544/issn1000-1239.2016.20160685]
[16]LIN H Y,TZENG W G.An efficient solution to the millionaires’problem based on homomorphic encryption[C].In:Applied Cryptography and Network Security-ACNS 2005.Springer Berlin Heidelberg,2005:456-466.[DOI:10.1007/11496137_31]
[17]LI S D,WANG D S.Efficient secure multiparty computation based on homomorphic encryption[J].Acta Electronica Sinica,2013,41(4):798-803.[DOI:10.3969/j.issn.0372-2112.2013.04.029]李顺东,王道顺.基于同态加密的高效多方保密计算[J].电子学报,2013,41(4):798-803.[DOI:10.3969/j.issn.0372-2112.2013.04.029]
[18]ZUO X J,LI S D,YANG X L.An efficient homomorphic encryption based solution to millionaires’problem[J].Journal of Chinese Computer Systems,2017,38(3):455-459.左祥建,李顺东,杨晓莉.同态加密的百万富翁问题高效解决方案[J].小型微型计算机系统,2017,38(3):455-459.
[19]FREEDMAN M J,NISSIM K,PINKAS B.Efficient private matching and set intersection[C].In:Advances in Cryptology-EUROCRYPT 2004.Springer Berlin Heidelberg,2004:1-19.[DOI:10.1007/978-3-540-24676-3_1]
[20]KISSNER L,SONG D.Privacy-preserving set operations[C].In:Advances in Cryptology-CRYPTO 2005.Springer Berlin Heidelberg,2005:241-257.[DOI:10.1007/11535218_15]
[21]PINKAS B,SCHNEIDER T,ZOHNER M.Faster private set intersection based on OT extension[C].In:Proceedings of the 23rd USENIX Conference on Security Symposium.USENIX,2014:797-812.
[22]HAZAY C.Oblivious polynomial evaluation and secure set-intersection from algebraic PRFs[C].In:Theory of Cryptography-TCC 2015.Springer Berlin Heidelberg,2015:90-120.[DOI:10.1007/978-3-662-46497-7_4]
[23]LI S D,ZHOU S F,GUO Y M,et al.Secure set computing in cloud environment[J].Journal of Software,2016,27(6):1549-1565.[DOI:10.13328/j.cnki.jos.004996]李顺东,周素芳,郭奕旻,等.云环境下集合隐私计算[J].软件学报,2016,27(6):1549-1565.[DOI:10.13328/j.cnki.jos.004996]
[24]XIA F,YANG B,ZHANG M W,et al.Secure two-party computation for set intersection and set equality problems based on LWE[J].Journal of Electronics Information&Technology,2012,34(2):462-467.[DOI:10.3724/SP.J.1146.2011.00541]夏峰,杨波,张明武,等.基于LWE的集合相交和相等的两方保密计算[J].电子与信息学报,2012,34(2):462-467.[DOI:10.3724/SP.J.1146.2011.00541]
[25]SUN M H,GONG Z.A privacy-preserving outsourcing set union protocol[J].Journal of Cryptologic Research,2016,3(2):114-125.[DOI:10.13868/j.cnki.jcr.000114]孙茂华,宫哲.一种保护隐私集合并集外包计算协议[J].密码学报,2016,3(2):114-125.[DOI:10.13868/j.cnki.jcr.000114]
[26]CHEN Z H,LI S D,WANG D S,et al.Secure multiparty computation of set membership and its applications[J].Acta Electronica Sinica,2017,45(5):1109-1116.[DOI:10.3969/j.issn.0372-2112.2017.05.013]陈振华,李顺东,王道顺,等.集合成员关系的安全多方计算及其应用[J].电子学报,2017,45(5):1109-1116.[DOI:10.3969/j.issn.0372-2112.2017.05.013]
[27]TANG C M,SHI G H,YAO Z A.Secure multi-party computation protocol for sequencing problem[J].SCIENTIASINICA Informationis,2011,54(8):1654-1662.[DOI:10.1007/s11432-011-4272-1]唐春明,石桂花,姚正安.排序问题的安全多方计算协议[J].中国科学:信息科学,2011,41(7):789-797.[DOI:10.1007/s11432-011-4272-1]
[28]LIU W,LUO S S,CHEN P.Solution of secure multi-party multi-data raking problem based on ElGamal encryption[J].Journal on Communications,2007,28(11):1-5.[DOI:10.3321/j.issn:1000-436x.2007.11.001]刘文,罗守山,陈萍.利用ElGamal密码体制解决安全多方多数据排序问题[J].通信学报,2007,28(11):1-5.[DOI:10.3321/j.issn:1000-436x.2007.11.001]
[29]QIU M,LUO S S,LIU W,et al.A solution of secure multi-party multi-data ranking problem based on RSA encryption scheme[J].Acta Electronica Sinica,2009,37(5):1119-1123.[DOI:10.3321/j.issn:0372-2112.2009.05.037]邱梅,罗守山,刘文,等.利用RSA密码体制解决安全多方多数据排序问题[J].电子学报,2009,37(5):1119-1123.[DOI:10.3321/j.issn:0372-2112.2009.05.037]
[30]DOU J W,MA L,LI S D.Secure multi-party computation for minimum and its applications[J].Acta Electronica Sinica,2017,45(7):1715-1721.[DOI:10.3969/j.issn.0372-2112.2017.07.023]窦家维,马丽,李顺东.最小值问题的安全多方计算及其应用[J].电子学报,2017,45(7):1715-1721.[DOI:10.3969/j.issn.0372-2112.2017.07.023]
[31]GOLDREICH O,MICALI S,WIGDERSON A.How to play ANY mental game[C].In:Proceedings of the Nineteenth Annual ACM Conference on Theory of Computing.ACM,1987:218-229.[DOI:10.1145/28395.28420]
[32]GOLDREICH O.Foundations of Cryptography:Basic Applications[M].London:Cambridge University Press,2004:599-729.
[33]HOFFSTEIN J,PIPHER J,SILVERMAN J H.NTRU:A ring-based public key cryptosystem[C].In:Algorithmic Number Theory-ANTS 1998.Springer Berlin Heidelberg,1998:267-288.[DOI:10.1007/BFb0054868]
[34]DUCAS L,DURMUS A,LEPOINT T,et al.Lattice signatures and bimodal Gaussians[C].In:Advances in Cryptology-CRYPTO 2013.Springer Berlin Heidelberg,2013:40-56.[DOI:10.1007/978-3-642-40041-4_3]
[35]PEIKERT C.Lattice cryptography for the Internet[C].In:Post-Quantum Cryptography-PQCrypto 2014.Springer Berlin Heidelberg,2014:197-219.[DOI:10.1007/978-3-319-11659-4_12]
[36]DUAN R,GU C X,ZHU Y F,et al.Efficient identity-based fully homomorphic encryption over NTRU[J].Journal on Communications,2017,38(1):66-75.[DOI:10.11959/j.issn.1000-436x.2017008]段然,顾纯祥,祝跃飞,等.NTRU格上高效的基于身份的全同态加密体制[J].通信学报,2017,38(1):66-75.[DOI:10.11959/j.issn.1000-436x.2017008]
[37]LóPEZ-ALT A,TROMER E,VAIKUNTANATHAN V.On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[C].In:Proceedings of the 44th Annual ACM Symposium on Theory of Computing(STOC 2012).ACM,2012:1219-1234.[DOI:10.1145/2213977.2214086]
[38]RIVEST R L,ADLEMAN M L,DERTOUZOS M.On data banks and privacy homomorphisms[C].In:Foundations of Secure Computation.New York:Academic Press,1978:169-177.
[39]STEHLéD,STEINFELD R.Making NTRU as secure as worst-case problems over ideal lattices[C].In:Advances in Cryptology-EUROCRYPT 2011.Springer Berlin Heidelberg,2011:27-47.[DOI:10.1007/978-3-642-20465-4_4]