Asymmetric commutative encryption scheme based efficient solution to the millionaires' problem

Secure multiparty computation (SMC) is an important scheme in cryptography and can be applied in various real-life problems. The first SMC problem is the millionaires' problem which involves two-party secure computation. Because the efficiency of public key encryption scheme appears less than symmetric encryption scheme, most existing solutions based on public key cryptography to this problem is inefficient. Thus, a solution based on the symmetric encryption scheme has been proposed. Although it is claimed that this approach can be efficient and practical, we discover that there exist several severe security flaws in this solution. In this paper, we analyze the vulnerability of existing solutions, and propose a new scheme based on the Decisional Diffie-Hellman hypothesis (DDH). Our solution also uses two special encodings (0-encoding and 1-encoding) generated by our modified encoding method to reduce the computation cost of modular multiplications. 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.