Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Conference on Digital Information Management

Symmetric Encryption Solutions to Millionaire's Problem and Its Extension

Shundong Li, Dai Yiqi, Wang Daoshun, Ping Luo

Published Apr 1, 2007• 4 citations
Publisher

Abstract

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.

DOI
10.1109/icdim.2007.369247

Related papers

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

Meng Liu, Yun Luo, Priyadarsi Nanda +2 more

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.

Computational Intelligence•May 23, 2019•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

Secure Comparison Under Ideal/Real Simulation Paradigm

Chuan Zhao, Shengnan Zhao, Bo Zhang +3 more

Secure comparison problem, also known as Yao's Millionaires' problem, was introduced by Andrew Yao in 1982. It is a fundamental problem in secure multi-party computation. In this problem, two millionaires are interested in determining the richer one between them without revealing their actual wealth. Yao's millionaires' problem is a classic and fundamental problem in cryptography. The design of secure and efficient solutions to this problem provides effective building blocks for secure multi-party computation. However, only a few of the solutions in the literature have succeeded in resisting attacks of malicious adversaries, and none of these solutions has been proven secure in malicious model under ideal/real simulation paradigm. In this paper, we propose two secure solutions to Yao's millionaires' problem in the malicious model. One solution has full simulation security, and the other solution achieves onesided simulation security. Both protocols are only based on symmetric cryptography. Experimental results indicate that our protocols can securely solve Yao's millionaires' problem with high efficiency and scalability. Furthermore, our solutions show better performance than the state-of-the-art solutions in terms of complexity and security. Specifically, our solutions only require O(|U|) symmetric operations at most to achieve simulation-based security against malicious adversaries, where U denotes the universal set and |U| denotes the size of U.

IEEE Access•Jan 1, 2018•1 citation

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

Improved Protocol of Yao’s Millionaires Problem

Huiqiang Li, Zhengtao Jiang, Ting Yu +1 more

Secure multi-party computation is a hot research topic in cryptography in recent years, and has become an important research direction in cryptography. This paper studies the millionaires’ problem in secure multi-party computation, and its essence is a comparison issue about the size of two encrypted data. Yao offered a solution to the millionaires’ problem, but his protocol can’t accurately compare two numbers. We improved Yao’s protocol and proposed two generic protocols to solve the millionaires’ problem. Our first protocol has one more round of communication between participants than Yao’s, but our protocol can accurately compare the size of two numbers. The second protocol improved the first protocol, and only one round of communication is needed to get accurate comparison results. Finally, we realized the second protocol based on RSA encryption algorithm, and analyze the security under the semi-honest model.

IEEE/ACIS International Conference on Computer and Information Science (ICIS)•Jun 26, 2022•2 citations
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.
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.
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 comparison problem, also known as Yao's Millionaires' problem, was introduced by Andrew Yao in 1982. It is a fundamental problem in secure multi-party computation. In this problem, two millionaires are interested in determining the richer one between them without revealing their actual wealth. Yao's millionaires' problem is a classic and fundamental problem in cryptography. The design of secure and efficient solutions to this problem provides effective building blocks for secure multi-party computation. However, only a few of the solutions in the literature have succeeded in resisting attacks of malicious adversaries, and none of these solutions has been proven secure in malicious model under ideal/real simulation paradigm. In this paper, we propose two secure solutions to Yao's millionaires' problem in the malicious model. One solution has full simulation security, and the other solution achieves onesided simulation security. Both protocols are only based on symmetric cryptography. Experimental results indicate that our protocols can securely solve Yao's millionaires' problem with high efficiency and scalability. Furthermore, our solutions show better performance than the state-of-the-art solutions in terms of complexity and security. Specifically, our solutions only require O(|U|) symmetric operations at most to achieve simulation-based security against malicious adversaries, where U denotes the universal set and |U| denotes the size of U.
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.
Secure multi-party computation is a hot research topic in cryptography in recent years, and has become an important research direction in cryptography. This paper studies the millionaires’ problem in secure multi-party computation, and its essence is a comparison issue about the size of two encrypted data. Yao offered a solution to the millionaires’ problem, but his protocol can’t accurately compare two numbers. We improved Yao’s protocol and proposed two generic protocols to solve the millionaires’ problem. Our first protocol has one more round of communication between participants than Yao’s, but our protocol can accurately compare the size of two numbers. The second protocol improved the first protocol, and only one round of communication is needed to get accurate comparison results. Finally, we realized the second protocol based on RSA encryption algorithm, and analyze the security under the semi-honest model.