AN EFFICIENT HOMOMORPHIC ENCRYPTION BASED SOLUTION TO MILLIONAIRES’ PROBLEM

Main Article Content

HUIRU CHENG

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
CHENG, H. (2020). AN EFFICIENT HOMOMORPHIC ENCRYPTION BASED SOLUTION TO MILLIONAIRES’ PROBLEM. Asian Journal of Mathematics and Computer Research, 27(3), 11-24. Retrieved from https://ikprress.org/index.php/AJOMCOR/article/view/5343
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.