Efficient solution to the millionaires' problem based on asymmetric commutative encryption scheme. (23rd May 2019)

• Record Type: Journal Article
• Authors: Liu, Meng; Luo, Yun; Nanda, Priyadarsi; Yu, Shui; Zhang, Jianbing
• Other Names: Pang Shaoning guestEditor.; Zhang Xuyun guestEditor.; Ikeda Kazushi guestEditor.; Puthal Deepak guestEditor.; Li Jianxin guestEditor.; Sarrafzahed Abdolhossein guestEditor.
• Is Part Of: Computational intelligence. Volume 35:Number 3(2019)
• Page Start: 555
• Page End: 576
• Publication Date: 2019-05-23
• Subjects: commutative encryption -- millionaires' problem -- secure multiparty computation -- security analysis -- set‐inclusion problem; Artificial intelligence -- Periodicals; Computational linguistics -- Periodicals; 006.3
• DOI: 10.1111/coin.12218
• Languages: English
• ISSNs: 0824-7935

Abstract

Abstract: Secure multiparty computation is an important scheme in cryptography and can be applied in various real‐life problems. The first secure multiparty computation problem is the millionaires' problem, and its protocol is an important building block. Because of the less efficiency of public key encryption scheme, most existing solutions based on public key cryptography to this problem are inefficient. Thus, a solution based on the symmetric encryption scheme has been proposed. In this paper, we formally analyse the vulnerability of this solution, and propose a new scheme based on the decisional Diffie‐Hellman assumption. Our solution also uses 0‐encoding and 1‐encoding generated by our modified encoding method to reduce the computation cost. We implement the solution based on symmetric encryption scheme and our protocol. Extensive experiments are conducted to evaluate the efficiency of our solution, and the experimental results show that our solution can be much more efficient and be approximately 8000 times faster than the solution based on symmetric encryption scheme for a 32‐bit input and short‐term security. Moreover, our solution is also more efficient than the state‐of‐the‐art solution without precomputation and can also compare well with the state‐of‐the‐art protocol while the bit length of private inputs is large enough.