基于1-r编码的高效百万富翁问题协议及应用
|
摘要
安全多方计算是近年来国际密码学的研究热点,已经成为密码学的一个重要研究方向.本文研究的百万富翁问题是安全多方计算最基本、最重要的问题,其本质就是保密比较两数据的大小问题.然而,目前已有的方案效率低下,影响实际应用,而且,大多数方案不能区分两数是否相等这种情况.针对这些问题,本文首先给出一种新的1-r编码方法,应用这种方法和给定的全序集合对保密数据进行编码,构造一个向量,使得保密数据与所编码的向量是一一对应的.基于此,本文把百万富翁问题转化为计算此向量中两个元素的乘积问题,通过乘积结果区分两个保密数据的大小,进而解决了原问题.此外,因为要保护双方的隐私,所以本文利用同态加密算法,设计了一个解决百万富翁问题的高效协议,并在半诚实模型下利用模拟范例的方法证明了协议的安全性.分析表明,相比已有的方案,本文的新方案不仅简单、高效,还能够更加细粒度地进行比较.最后,以新方案为基础,构造了一个具有验证机制的百万富翁协议,并应用协议1设计一个高效的保密查询数据在有序集合中排序的协议.
Secure multi-party computation is a research hotspot in cryptography in recent years, and has become an important research direction. A millionaires' problem studied in this work is the most basic and important problem of secure multi-party computation, and its essence is a comparison issue about the size of two encrypted data. However, so far existing solutions are inefficient, and do not suit practical applications. Meanwhile, most existing schemes do not distinguish whether the two numbers are equal. Aiming at these issues, this study proposes a new 1-r encoding. A vector was constructed by applying this method and a given total ordered set to encode the confidential data, which guaranteed a one-to-one mapping between the confidential data and the vector. Based on this, the Millionaires' problem can be transformed into product problem between two elements in the vector. The problem can be solved by computing the product to distinguish the size of two encrypted values. In addition,since the privacy of both parties needs to be protected, a new efficient protocol is designed to solve the Millionaires' problem by taking advantage of a homomorphic encryption algorithm; the security of the protocol, in the semi-honest model, is proven by using the method of simulation paradigm. The analysis indicated that, compared with the existing schemes, the new scheme is simple and efficient, and the comparison was more fine-grained. Furthermore, a new millionaires' problem protocol is designed providing authentication mechanism, and a protocol is designed which can query the data ranking in an ordered set.
Secure multi-party computation is a research hotspot in cryptography in recent years, and has become an important research direction. A millionaires' problem studied in this work is the most basic and important problem of secure multi-party computation, and its essence is a comparison issue about the size of two encrypted data. However, so far existing solutions are inefficient, and do not suit practical applications. Meanwhile, most existing schemes do not distinguish whether the two numbers are equal. Aiming at these issues, this study proposes a new 1-r encoding. A vector was constructed by applying this method and a given total ordered set to encode the confidential data, which guaranteed a one-to-one mapping between the confidential data and the vector. Based on this, the Millionaires' problem can be transformed into product problem between two elements in the vector. The problem can be solved by computing the product to distinguish the size of two encrypted values. In addition,since the privacy of both parties needs to be protected, a new efficient protocol is designed to solve the Millionaires' problem by taking advantage of a homomorphic encryption algorithm; the security of the protocol, in the semi-honest model, is proven by using the method of simulation paradigm. The analysis indicated that, compared with the existing schemes, the new scheme is simple and efficient, and the comparison was more fine-grained. Furthermore, a new millionaires' problem protocol is designed providing authentication mechanism, and a protocol is designed which can query the data ranking in an ordered set.
引文
[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]GOLDREICH O,MICALI S,WIGDERSON A.How to play any mental game[C].In:Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing.ACM,1987:218-229.[DOI:10.1145/28395.28420]
[3]GOLDREICH O.Foundations of Cryptography:Basic Applications[M].London:Cambridge University Press,2004:599-729.
[4]YAO A C.How to generate and exchange secrets[C].In:Proceedings of 27th Annual Symposium on Foundations of Computer Science(FOCS’86).IEEE,1986:162-167.[DOI:10.1109/sfcs.1986.25]
[5]DU W L,ATALLAH M J.Secure multi-party computation problems and their applications:A review and open problems[C].In:Proceedings of the 2001 Workshop on New Security Paradigms(NSPW’01).ACM,2001:13-22.[DOI:10.1145/508171.508174]
[6]LI S D,WANG D S,DAI Y Q,et al.Symmetric cryptographic solution to Yao’s millionaires’problem and an evaluation of secure multiparty computations[J].Information Sciences,2008,178(1):244-255.[DOI:10.1016/j.ins.2007.07.015]
[7]IOANNIDIS I,GRAMA A.An efficient protocol for Yao’s millionaires’problem[C].In:Proceedings of the 36th Hawaii International Conference on System Sciences.HI,USA,2003:6-9.[DOI:10.1109/HICSS.2003.1174464]
[8]SCHOENMAKERS B,TUYLS P.Practical two-party computation based on the conditional gate[C].In:Advances in Cryptology-ASIACRYPT 2004.Springer Berlin Heidelberg,2004:119-136.[DOI:10.1007/978-3-540-30539-2_10]
[9]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]
[10]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]
[11]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.
[12]DU W,ATALLAH M J.Privacy-preserving cooperative statistical analysis[C].In:Proceedings of Seventeenth Annual Computer Security Applications Conference.New Orleans,LA,USA,2001:102-110.[DOI:10.1109/AC-SAC.2001.991526]
[13]TANG C M,SHI G G,YAO Z A.Secure multi-party computation protocol for sequencing problem[J].Science China Information Sciences,2011,54(8):1654-1662.[DOI:10.1007/s11432-011-4272-1]
[14]LIU W,WANG Y B.Secure multi-party comparing protocol and its applications[J].Acta Electronica Sinica,2012,40(5):871-876.[DOI:10.3969/j.issn.0372-2112.2012.05.002]刘文,王永滨.安全多方信息比较相等协议及其应用[J].电子学报,2012,40(5):871-876.[DOI:10.3969/j.issn.0372-2112.2012.05.002]
[15]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]
[16]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]
[17]DU W L,ATALLAH M J.Privacy-preserving cooperative scientific computations[C].In:Proceedings of 14th IEEEComputer Security Foundations Workshop.IEEE Press,2001:273-282.[DOI:10.1109/CSFW.2001.930152]
[18]AGRAWAL D,AGGARWAL C C.On the design and quantification of privacy preserving data mining algorithms[C].In:Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems.Santa Barbara,CA,USA.2001:247-255.[DOI:10.1145/375551.375602]
[19]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]
[20]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]
[21]AGGARWAL C C.Privacy-preserving data mining[M].In:Data Mining.Springer Cham,2015:663-693.[DOI:10.1007/978-3-319-14142-8_20]
[22]SAMANTHULA B K,ELMEHDWI Y,HOWSER G,et al.A secure data sharing and query processing framework via federation of cloud computing[J].Information Systems,2015,48:196-212.[DOI:10.1016/j.is.2013.08.004]
[23]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]
[24]CHEN Z H,LI S D,HUANG Qiong,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]
[25]HU X,TANG C M.Securely outsourcing computation of point multiplication on elliptic curves in cloud computing[J].Journal of Hunan University of Science and Technology(Natural Science Edition),2014(1):119-123.[DOI:10.13582/j.cnki.1672-9102.2014.01.024]胡杏,唐春明.云环境下安全外包椭圆曲线点的乘法[J].湖南科技大学学报(自然科学版),2014(1):119-123.[DOI:10.13582/j.cnki.1672-9102.2014.01.024]
[26]EL GAMAL T.A public key cryptosystem and a signature scheme based on discrete logarithms[J].IEEE Transactions on Information Theory,1984,31(4):469-472.[DOI:10.1109/TIT.1985.1057074]
[27]RIVEST R L,ADLEMAN L,DERTOUZOS M L.On data banks and privacy homomorphisms[J].Foundations of Secure Computation,1978,4(11):169-180.
[2]GOLDREICH O,MICALI S,WIGDERSON A.How to play any mental game[C].In:Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing.ACM,1987:218-229.[DOI:10.1145/28395.28420]
[3]GOLDREICH O.Foundations of Cryptography:Basic Applications[M].London:Cambridge University Press,2004:599-729.
[4]YAO A C.How to generate and exchange secrets[C].In:Proceedings of 27th Annual Symposium on Foundations of Computer Science(FOCS’86).IEEE,1986:162-167.[DOI:10.1109/sfcs.1986.25]
[5]DU W L,ATALLAH M J.Secure multi-party computation problems and their applications:A review and open problems[C].In:Proceedings of the 2001 Workshop on New Security Paradigms(NSPW’01).ACM,2001:13-22.[DOI:10.1145/508171.508174]
[6]LI S D,WANG D S,DAI Y Q,et al.Symmetric cryptographic solution to Yao’s millionaires’problem and an evaluation of secure multiparty computations[J].Information Sciences,2008,178(1):244-255.[DOI:10.1016/j.ins.2007.07.015]
[7]IOANNIDIS I,GRAMA A.An efficient protocol for Yao’s millionaires’problem[C].In:Proceedings of the 36th Hawaii International Conference on System Sciences.HI,USA,2003:6-9.[DOI:10.1109/HICSS.2003.1174464]
[8]SCHOENMAKERS B,TUYLS P.Practical two-party computation based on the conditional gate[C].In:Advances in Cryptology-ASIACRYPT 2004.Springer Berlin Heidelberg,2004:119-136.[DOI:10.1007/978-3-540-30539-2_10]
[9]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]
[10]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]
[11]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.
[12]DU W,ATALLAH M J.Privacy-preserving cooperative statistical analysis[C].In:Proceedings of Seventeenth Annual Computer Security Applications Conference.New Orleans,LA,USA,2001:102-110.[DOI:10.1109/AC-SAC.2001.991526]
[13]TANG C M,SHI G G,YAO Z A.Secure multi-party computation protocol for sequencing problem[J].Science China Information Sciences,2011,54(8):1654-1662.[DOI:10.1007/s11432-011-4272-1]
[14]LIU W,WANG Y B.Secure multi-party comparing protocol and its applications[J].Acta Electronica Sinica,2012,40(5):871-876.[DOI:10.3969/j.issn.0372-2112.2012.05.002]刘文,王永滨.安全多方信息比较相等协议及其应用[J].电子学报,2012,40(5):871-876.[DOI:10.3969/j.issn.0372-2112.2012.05.002]
[15]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]
[16]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]
[17]DU W L,ATALLAH M J.Privacy-preserving cooperative scientific computations[C].In:Proceedings of 14th IEEEComputer Security Foundations Workshop.IEEE Press,2001:273-282.[DOI:10.1109/CSFW.2001.930152]
[18]AGRAWAL D,AGGARWAL C C.On the design and quantification of privacy preserving data mining algorithms[C].In:Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems.Santa Barbara,CA,USA.2001:247-255.[DOI:10.1145/375551.375602]
[19]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]
[20]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]
[21]AGGARWAL C C.Privacy-preserving data mining[M].In:Data Mining.Springer Cham,2015:663-693.[DOI:10.1007/978-3-319-14142-8_20]
[22]SAMANTHULA B K,ELMEHDWI Y,HOWSER G,et al.A secure data sharing and query processing framework via federation of cloud computing[J].Information Systems,2015,48:196-212.[DOI:10.1016/j.is.2013.08.004]
[23]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]
[24]CHEN Z H,LI S D,HUANG Qiong,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]
[25]HU X,TANG C M.Securely outsourcing computation of point multiplication on elliptic curves in cloud computing[J].Journal of Hunan University of Science and Technology(Natural Science Edition),2014(1):119-123.[DOI:10.13582/j.cnki.1672-9102.2014.01.024]胡杏,唐春明.云环境下安全外包椭圆曲线点的乘法[J].湖南科技大学学报(自然科学版),2014(1):119-123.[DOI:10.13582/j.cnki.1672-9102.2014.01.024]
[26]EL GAMAL T.A public key cryptosystem and a signature scheme based on discrete logarithms[J].IEEE Transactions on Information Theory,1984,31(4):469-472.[DOI:10.1109/TIT.1985.1057074]
[27]RIVEST R L,ADLEMAN L,DERTOUZOS M L.On data banks and privacy homomorphisms[J].Foundations of Secure Computation,1978,4(11):169-180.