© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Computational Intelligence

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

Meng Liu, Yun Luo, Priyadarsi Nanda, Shui Yu, Jianbing Zhang

Published May 23, 2019• 4 citations

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.

DOI: 10.1111/coin.12218

Related papers

Symmetric Encryption Solutions to Millionaire's Problem and Its Extension

Shundong Li, Dai Yiqi, Wang Daoshun +1 more

Millionaire's problem is the base of secure multiparty computation, and its solutions have become basic blocks of many secure multi-party computation solutions. Unfortunately, most solutions to millionaire's problem are based on public key cryptography, and thus are inefficient. Furthermore, all solutions are designed to solve millionaire's problem for natural number case to privately determine which natural number is larger. If the numbers are real, these solutions do not directly work. In this paper, we first propose a symmetric key cryptographic solution to millionaire's problem for natural numbers case, and then generalize it to the case of real numbers, that is to privately determine which real number is larger. We further prove, by simulation paradigm, that these solutions are private. These solutions are really efficient.

International Conference on Digital Information Management•Apr 1, 2007•4 citations

Protocol for millionaires' problem in malicious models

顺东 LI, 文丽 WANG, 润萌 DU

Secure multiparty computation is a focus of the international cryptographic community. The millionaires problem is the most important problem in secure multiparty computation and is a building block for constructing other secure multiparty computation protocols. Several solutions are available to solve this problem, but except for protocols based on garbled circuits, the existing solutions based on public key cryptosystems are only secure in semihonest models. No solution based on a public key cryptosystem is secure against malicious adversaries. This state restricts the resolution of many secure multiparty computation problems in malicious scenarios. A solution that is secure in malicious models is highly applicable in practical application scenarios and is generally appealing. Therefore, the study of the solution to the millionaires problem in a malicious model is of great theoretical and practical significance. In this work, we propose a multiparty computation protocol for the millionaires problem that is secure in a semihonest model. The proposed protocol is simple and easily understandable. We analyze the possible malicious behaviors in this protocol and use zero-knowledge proof and cut-and-choose techniques to resist possible malicious behaviors and thereby convert the protocol into one that is secure in the malicious model. We prove that the proposed protocol is secure in the malicious model by using the well-accepted ideal-real paradigm. Theoretical efficiency analysis shows that the efficiency of our protocol is at least six times that of existing protocols.

Scientia Sinica Informationis•Dec 22, 2020•21 citations

Efficient Secure Multiparty Computation Based on Homomorphic Encryption

Daoshun Wang

Secure multiparty computation is a key privacy-preserving technology in cyberspaces and a research focus in the international cryptographic community.We first present a new encoding scheme to encode private data.By using this encoding scheme together with homomorphic encryption scheme,we construct a new scheme for Yao′s millionaires′ problem and prove its privacy-preserving property.This new scheme is more concise,more general and can be applied to compare any two objects on which a total order can be defined.We finally utilize the new scheme to propose a solution to the coprime problem and prove the privacy-preserving properties of the solution.

Dianzi xuebao•Jan 1, 2013•4 citations

Efficient Solutions to Two-Party and Multiparty Millionaires’ Problem

Xin Liu, Shundong Li, Xiu‐Bo Chen +3 more

The millionaires’ problem is the basis of secure multiparty computation and has many applications. Using a vectorization method and the Paillier encryption scheme, we first propose a secure two-party solution to the millionaires’ problem, which can determine x=y, x<y , or x>y in one execution. Subsequently, using the vectorization and secret splitting methods, we propose an information-theoretically secure protocol to solve the multiparty millionaires’ problem (a.k.a. secure sorting problem), and this protocol can resist collusion attacks. We analyze the accuracy and security of our protocols in the semihonest model and compare the computational and communication complexities between the proposed protocols and the existing ones.

Security and Communication Networks•Jan 1, 2017•23 citations

Efficient Protocols for the General Millionaires' Problem

Shundong Li, Yimin Guo, Sufang Zhou +2 more

Secure multiparty computation (SMC) is a research focusing in the international cryptographic community. The protocols used to address the millionaires' problem are the basic building blocks of most SMC protocols and their efficiency dominates that of many other SMC protocols. To the best of our knowledge, almost all protocols used to address the millionaires' problem are based on integers, which means that their applications are limited. In this study, we propose precise and efficient protocols for rational numbers based on additively homomorphic encryptions. One of our protocols is inspired by computational geometry and it reduces the millionaires problem to computing the area of a triangle formed by three private points. This approach can determine whether the relationship between two private inputs is greater than, equal to or less than, and it has a much lower computational complexity compared with existing methods. We proved that these protocols are secure using simulation paradigm. Our approaches can be used in many SMC protocols that involve rational numbers and integers, and they can also be used directly to solve some secure multiparty computational geometry problem in rational number field.

Chinese Journal of Electronics•Jul 1, 2017•10 citations

An Efficient Solution to Yao's Millionaires' Problem

You Qi-you

AbstrcatThe protocols for Yao's Millionaires' problem have been building blocks of solutions to many secure multi-party computation problems.But known solutions are not efficient enough and thus affect the efficiency of many secure multi-party computation protocols.In this paper,we construct a new efficient solution to millionaires' problem based on length function and oblivious transfer.Compared with known solutions,our new solution has much less computational complexity.

Dianzi xuebao•Jan 1, 2005•7 citations

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.

Millionaire's problem is the base of secure multiparty computation, and its solutions have become basic blocks of many secure multi-party computation solutions. Unfortunately, most solutions to millionaire's problem are based on public key cryptography, and thus are inefficient. Furthermore, all solutions are designed to solve millionaire's problem for natural number case to privately determine which natural number is larger. If the numbers are real, these solutions do not directly work. In this paper, we first propose a symmetric key cryptographic solution to millionaire's problem for natural numbers case, and then generalize it to the case of real numbers, that is to privately determine which real number is larger. We further prove, by simulation paradigm, that these solutions are private. These solutions are really efficient.

Secure multiparty computation is a focus of the international cryptographic community. The millionaires problem is the most important problem in secure multiparty computation and is a building block for constructing other secure multiparty computation protocols. Several solutions are available to solve this problem, but except for protocols based on garbled circuits, the existing solutions based on public key cryptosystems are only secure in semihonest models. No solution based on a public key cryptosystem is secure against malicious adversaries. This state restricts the resolution of many secure multiparty computation problems in malicious scenarios. A solution that is secure in malicious models is highly applicable in practical application scenarios and is generally appealing. Therefore, the study of the solution to the millionaires problem in a malicious model is of great theoretical and practical significance. In this work, we propose a multiparty computation protocol for the millionaires problem that is secure in a semihonest model. The proposed protocol is simple and easily understandable. We analyze the possible malicious behaviors in this protocol and use zero-knowledge proof and cut-and-choose techniques to resist possible malicious behaviors and thereby convert the protocol into one that is secure in the malicious model. We prove that the proposed protocol is secure in the malicious model by using the well-accepted ideal-real paradigm. Theoretical efficiency analysis shows that the efficiency of our protocol is at least six times that of existing protocols.

Secure multiparty computation is a key privacy-preserving technology in cyberspaces and a research focus in the international cryptographic community.We first present a new encoding scheme to encode private data.By using this encoding scheme together with homomorphic encryption scheme,we construct a new scheme for Yao′s millionaires′ problem and prove its privacy-preserving property.This new scheme is more concise,more general and can be applied to compare any two objects on which a total order can be defined.We finally utilize the new scheme to propose a solution to the coprime problem and prove the privacy-preserving properties of the solution.

The millionaires’ problem is the basis of secure multiparty computation and has many applications. Using a vectorization method and the Paillier encryption scheme, we first propose a secure two-party solution to the millionaires’ problem, which can determine x=y, x<y , or x>y in one execution. Subsequently, using the vectorization and secret splitting methods, we propose an information-theoretically secure protocol to solve the multiparty millionaires’ problem (a.k.a. secure sorting problem), and this protocol can resist collusion attacks. We analyze the accuracy and security of our protocols in the semihonest model and compare the computational and communication complexities between the proposed protocols and the existing ones.

Secure multiparty computation (SMC) is a research focusing in the international cryptographic community. The protocols used to address the millionaires' problem are the basic building blocks of most SMC protocols and their efficiency dominates that of many other SMC protocols. To the best of our knowledge, almost all protocols used to address the millionaires' problem are based on integers, which means that their applications are limited. In this study, we propose precise and efficient protocols for rational numbers based on additively homomorphic encryptions. One of our protocols is inspired by computational geometry and it reduces the millionaires problem to computing the area of a triangle formed by three private points. This approach can determine whether the relationship between two private inputs is greater than, equal to or less than, and it has a much lower computational complexity compared with existing methods. We proved that these protocols are secure using simulation paradigm. Our approaches can be used in many SMC protocols that involve rational numbers and integers, and they can also be used directly to solve some secure multiparty computational geometry problem in rational number field.