© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Hawaii International Conference on System Sciences (HICSS)

An efficient protocol for Yao's millionaires' problem

I. Ioannidis, Ananth Y. Grama

Published Jan 1, 2003• 109 citations

Abstract

The increase in volume and sensitivity of data communicated and processed over the Internet has been accompanied by a corresponding need for e-commerce techniques in which entities can participate in a secure and anonymous fashion. Even simple arithmetic operations over a set of integers partitioned over a network require sophisticated algorithms. As apart of our earlier work, we have developed a secure protocol for computing dot products of two vectors. In this paper, we present a secure protocol for Yao's millionaires' problem. In this problem, each of the two participating parties have a number and the objective is to determine whose number is larger without disclosing any information about the numbers. This problem has direct applications in on-line bidding and auctions. Furthermore, combined with a secure dot-product, a solution to this secure multiparty computation provides necessary building blocks for such basic operations as frequent item-set generation in association rule mining. Although an asymptotically optimal solution for the secure multiparty computation of the 'less-or-equal' predicate exists in literature, this protocol is not suited for practical applications. Here, we present a protocol which has a much simpler structure and is more efficient for numbers in ranges practically encountered in typical e-commerce applications. Furthermore, advances in cryptanalysis and the subsequent increase in key lengths for public-key cryptographic systems accentuate the advantage of the proposed protocol. We present experimental evidence demonstrating the efficiency of the proposed protocol both in terms of time and communication overhead.

DOI: 10.1109/hicss.2003.1174464

Related papers

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

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

Secure two party comparison over encrypted data

Parisa Kaghazgaran, Sadeghyan Babak

Yao's classical millionaires' problem is about securely determining whether x>y, given two input values x, y, which are held as private inputs by two parties, respectively. The output which is result of comparison becomes known to both parties. In this paper we consider a variant of comparison problem in which the inputs x, y are encrypted and the actual values are not known to the parties. Our first solution deals with single comparison; however, in many applications, we encounter situations where it is necessary to make multiple comparisons to find the maximum among several encrypted data, so we make a modification to our first protocol to solve the multiple comparisons problem. Such a secure comparison is an important building block for applications like privacy preserving data mining and secure business. Our second protocol is based on Homomorphic encryption which achieves very low communication and computational complexities. Also our protocols can be performed in constant rounds and do not use general circuit evaluation techniques so they are more efficient than circuit based ones but not general. Implementation is easy and fast.

World Congress on Information and Communication Technologies•Dec 1, 2011•10 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

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

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

The increase in volume and sensitivity of data communicated and processed over the Internet has been accompanied by a corresponding need for e-commerce techniques in which entities can participate in a secure and anonymous fashion. Even simple arithmetic operations over a set of integers partitioned over a network require sophisticated algorithms. As apart of our earlier work, we have developed a secure protocol for computing dot products of two vectors. In this paper, we present a secure protocol for Yao's millionaires' problem. In this problem, each of the two participating parties have a number and the objective is to determine whose number is larger without disclosing any information about the numbers. This problem has direct applications in on-line bidding and auctions. Furthermore, combined with a secure dot-product, a solution to this secure multiparty computation provides necessary building blocks for such basic operations as frequent item-set generation in association rule mining. Although an asymptotically optimal solution for the secure multiparty computation of the 'less-or-equal' predicate exists in literature, this protocol is not suited for practical applications. Here, we present a protocol which has a much simpler structure and is more efficient for numbers in ranges practically encountered in typical e-commerce applications. Furthermore, advances in cryptanalysis and the subsequent increase in key lengths for public-key cryptographic systems accentuate the advantage of the proposed protocol. We present experimental evidence demonstrating the efficiency of the proposed protocol both in terms of time and communication overhead.

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 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.

Yao's classical millionaires' problem is about securely determining whether x>y, given two input values x, y, which are held as private inputs by two parties, respectively. The output which is result of comparison becomes known to both parties. In this paper we consider a variant of comparison problem in which the inputs x, y are encrypted and the actual values are not known to the parties. Our first solution deals with single comparison; however, in many applications, we encounter situations where it is necessary to make multiple comparisons to find the maximum among several encrypted data, so we make a modification to our first protocol to solve the multiple comparisons problem. Such a secure comparison is an important building block for applications like privacy preserving data mining and secure business. Our second protocol is based on Homomorphic encryption which achieves very low communication and computational complexities. Also our protocols can be performed in constant rounds and do not use general circuit evaluation techniques so they are more efficient than circuit based ones but not general. Implementation is easy and fast.

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.

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.