AN EFFICIENT HOMOMORPHIC ENCRYPTION BASED SOLUTION TO MILLIONAIRES’ PROBLEM
Article Sidebar
Published:
Aug 25, 2020
Page:
11-24
Main Article Content
HUIRU CHENG
College of Science, North China University of Technology, Beijing 100144, P. R. China.
Abstract
Secure multi-party computation is an important research direction of international cryptography in recent years. The millionaires’ problem studied in this paper is the most basic and important problem of secure multi-party computation. The essence is to compare the size of two data confidentially. But most of the existing solutions are inefficient, and most of them don't do a good job of judging if the two data are equal. In order to design a protocol of the millionaires’ problem that is simple, efficient and meticulous distinction between the size of two numbers or equal relationship, this paper firstly proposes a new method based on 0-1 coding to encode the encrypted data. This method and the homomorphic encryption algorithm are used to design a protocol to solve the millionaires’ problem. The efficiency analysis shows that the protocol is simple and efficient. Finally, based on the new protocol, an efficient protocol is designed to calculate the number of intersections problem.
Keywords:
Secure multi-party computation, millionaires’ problem, homomorphic encryption, number of set intersections
Article Details
How to Cite
Section
Original Research Article
References
Yao AC. Protocols for secure computations[C]. In: Proceeding of the 23th IEEE Annual Symposium on Foundations of Computer Science. IEEE. 1982;160-164.
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
Goldreich O. The Foundation of Cryptography-Volume 2, Basic Applications. Cambridge: Cambridge University Press, 2004: 599-729.
Yao AC. 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
Du WL, Atallah MJ. 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
Li SD, Wang DS, Dai YQ, 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
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
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
Lin HY, Tzeng WG. 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
Li SD, Wang DS. 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
Zuo XJ, Li SD, Yang XL. An efficient homomorphic encryption based solution to millionaires’ problem[J]. Journal of Chinese Computer Systems. 2017;38(3):455–459.
Li ZL, Chen LC, Chen ZH, Liu YR, Gao T. Design and applications of efficient protocol of millionaires’ problem based on 1-r encoding[J]. Journal of Cryptologic Research. 2019;6(1):50–60.
Tang CM, Shi GH, Yao ZA. Secure multi-party computation protocol for sequencing problem[J]. SCIENTIA SINICA Informationis. 2011;54(8):1654–1662.
DOI: 10.1007/s11432-011-4272-1
Freedman MJ, Nissim K, Pinkasb. Efficient private matching and set Intersection[C]. In: Advanced Cryptology-EUROCRYPT. Berlin Heidelberg: Springer. 2004;1-19.
DOI: 10.1007//978-3-540-24676-3_1
Liu W, Wang YB. Secure Multi-Party Comparing Protocol and Its Applications [J]. 2012;40(5):871–876．
DOI: 10.3969/j.issn.0372
Kissner L, Song D. Privacy-preserving set operations [C]. Advanced Cryptology-CRYPTO [C]. Berlin Heidelberg: Springer. 2005;241-257.
DOI:10.1007/11535318_15
Du WL, Atallah MJ. 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
Aldeen YAAS, Salleh M, Razzaque MA. A comprehensive review on privacy preserving data mining[J]. Springerplus. 2015;4(1):694.
DOI: 10.1186/s40064-015-1481-x
Agrawal D, Aggarwal CC. 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
Ge X, Wang YN, Dou JW. Histogram and pie chart of confidentiality generation agree-ment[J]. Journal of Cryptologic Research. 2019;6(02):234–245.
DOI: 10.13868/j.cnki.jcr.000298
Du W, Atallah MJ. Privacy-preserving cooperative statistical analysis[C]// Computer Security Applications Conference. IEEE Computer Society; 2002.
DOI: 10.1109/ACSAC.2001.991526
Atallah MJ, Du W. Secure multi-party computational geometry[C]. In: Algorithms and Data Structures-WADS 2001. Springer Berlin Heidelberg. 2001;165-179.
DOI: 10.1007/3-540-44634-6_16
Li SD, Wu CY, Wang DS, Dai YQ. Secure multiparty computation of solid geometric problems and their applications[J]. Information Sciences. 2014;282:401-413.
DOI: 10.1016/j.ins.2014.04.004
Qin J, Duan H, Zhao H, et al. A new lagrange solution to the privacy-preserving general geometric intersection problem[J]. Journal of Network and Computer Applications. 2014;46:94-99.
DOI: 10.1016/j.jnca.201408.004
Samanthula BK, 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
Loftus J, Smart NP. Secure outsourced computation[C]. In: Progress in Cryptology-africacrypt -international Conference on Cryptology in Africa. DBLP. 2011;1-20.
DOI: 10.1007/978-3-642-21969-6_1
Chen ZH, Li SD, 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
Hu X, Tang CM. Scurely 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
Duan J, Zhou JT, Li YM. Privacy-preserving distributed deep learning based on secret sharing[J]. Information Sciences. 2020;5:108-127.
DOI: 10.1016/j.ins.3030.0374
Rong M, Yi L, Chenxing L, et al. Secure multiparty computation for privacy-preserving drug discovery [J]. Bioinformatics. 2020;9(9):2872-2880.
DOI: 10.1093/bioinformatics/btaa038
Rivest RL, Dertouzos ML. On data banks and privacy homomorphic [J]. Foundations of Secure Computation. 1978;4(11):169-180.
Paillier P. Public-key cryptosystems based on composite degree residuosity classes [C]. Proceedings of the 17th International Conference on Theory and Application of Cryptographic Techniques, Spring-Verlag. 1999;223-238.
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
Goldreich O. The Foundation of Cryptography-Volume 2, Basic Applications. Cambridge: Cambridge University Press, 2004: 599-729.
Yao AC. 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
Du WL, Atallah MJ. 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
Li SD, Wang DS, Dai YQ, 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
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
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
Lin HY, Tzeng WG. 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
Li SD, Wang DS. 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
Zuo XJ, Li SD, Yang XL. An efficient homomorphic encryption based solution to millionaires’ problem[J]. Journal of Chinese Computer Systems. 2017;38(3):455–459.
Li ZL, Chen LC, Chen ZH, Liu YR, Gao T. Design and applications of efficient protocol of millionaires’ problem based on 1-r encoding[J]. Journal of Cryptologic Research. 2019;6(1):50–60.
Tang CM, Shi GH, Yao ZA. Secure multi-party computation protocol for sequencing problem[J]. SCIENTIA SINICA Informationis. 2011;54(8):1654–1662.
DOI: 10.1007/s11432-011-4272-1
Freedman MJ, Nissim K, Pinkasb. Efficient private matching and set Intersection[C]. In: Advanced Cryptology-EUROCRYPT. Berlin Heidelberg: Springer. 2004;1-19.
DOI: 10.1007//978-3-540-24676-3_1
Liu W, Wang YB. Secure Multi-Party Comparing Protocol and Its Applications [J]. 2012;40(5):871–876．
DOI: 10.3969/j.issn.0372
Kissner L, Song D. Privacy-preserving set operations [C]. Advanced Cryptology-CRYPTO [C]. Berlin Heidelberg: Springer. 2005;241-257.
DOI:10.1007/11535318_15
Du WL, Atallah MJ. 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
Aldeen YAAS, Salleh M, Razzaque MA. A comprehensive review on privacy preserving data mining[J]. Springerplus. 2015;4(1):694.
DOI: 10.1186/s40064-015-1481-x
Agrawal D, Aggarwal CC. 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
Ge X, Wang YN, Dou JW. Histogram and pie chart of confidentiality generation agree-ment[J]. Journal of Cryptologic Research. 2019;6(02):234–245.
DOI: 10.13868/j.cnki.jcr.000298
Du W, Atallah MJ. Privacy-preserving cooperative statistical analysis[C]// Computer Security Applications Conference. IEEE Computer Society; 2002.
DOI: 10.1109/ACSAC.2001.991526
Atallah MJ, Du W. Secure multi-party computational geometry[C]. In: Algorithms and Data Structures-WADS 2001. Springer Berlin Heidelberg. 2001;165-179.
DOI: 10.1007/3-540-44634-6_16
Li SD, Wu CY, Wang DS, Dai YQ. Secure multiparty computation of solid geometric problems and their applications[J]. Information Sciences. 2014;282:401-413.
DOI: 10.1016/j.ins.2014.04.004
Qin J, Duan H, Zhao H, et al. A new lagrange solution to the privacy-preserving general geometric intersection problem[J]. Journal of Network and Computer Applications. 2014;46:94-99.
DOI: 10.1016/j.jnca.201408.004
Samanthula BK, 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
Loftus J, Smart NP. Secure outsourced computation[C]. In: Progress in Cryptology-africacrypt -international Conference on Cryptology in Africa. DBLP. 2011;1-20.
DOI: 10.1007/978-3-642-21969-6_1
Chen ZH, Li SD, 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
Hu X, Tang CM. Scurely 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
Duan J, Zhou JT, Li YM. Privacy-preserving distributed deep learning based on secret sharing[J]. Information Sciences. 2020;5:108-127.
DOI: 10.1016/j.ins.3030.0374
Rong M, Yi L, Chenxing L, et al. Secure multiparty computation for privacy-preserving drug discovery [J]. Bioinformatics. 2020;9(9):2872-2880.
DOI: 10.1093/bioinformatics/btaa038
Rivest RL, Dertouzos ML. On data banks and privacy homomorphic [J]. Foundations of Secure Computation. 1978;4(11):169-180.
Paillier P. Public-key cryptosystems based on composite degree residuosity classes [C]. Proceedings of the 17th International Conference on Theory and Application of Cryptographic Techniques, Spring-Verlag. 1999;223-238.