Efficient solution to the millionaires' problem based on asymmetric commutative encryption scheme

摘要

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.