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

arXiv:1504.01974

Millionaires' Problem with Rational Players: a Unified Approach in Classical and Quantum Paradigms.

Arpita Maitra, Goutam Paul, Asim Kumar Pal

Published Apr 8, 2015• 3 citations
arXivHTMLPDF

Abstract

A seminal result of Cleve (STOC 1986) showed that fairness, in general, is impossible to achieve in case of two-party computation if one of them is malicious. Gordon et al. (STOC 2008) observed that there exist some functions for which fairness can be achieved even though one of the two parties is malicious. One of the functions considered by Gordon et al. is exactly the millionaires' problem (Yao, FOCS 1982) or, equivalently, the `greater than' function. The problem deals with two millionaires, Alice and Bob, who are interested in finding who amongst them is richer, without revealing their actual wealth to each other. We, for the first time, study this problem in presence of rational players. In particular, we show that Gordon's protocol no longer remains fair when the players are rational. Next, we design a protocol with rational players, that not only achieves fairness, but also achieves correctness and strict Nash equilibrium for natural utilities. We, also for the first time, provide a solution to the quantum version of millionaires' problem with rational players, and it too achieves fairness, correctness and strict Nash equilibrium. Both our classical and quantum protocols follow an unified approach; both uses an untrusted third party (UTP) and exploits the idea of interlocking system between the players, to prevent the deviating party to abort early. In both the protocols, we remove the requirement of the online dealer of Groce et al. (EUROCRYPT 2012).

Related papers

Fairness in Secure Two-Party Computation with Rational Players.

Arpita Maitra, Goutam Paul, Asim Kumar Pal

A seminal result of Cleve (STOC 1986) showed that fairness, in general, is impossible to achieve in case of two-party computation if one of them is malicious. Later, Gordon et al. (STOC 2008) observed that there exist some functions for which fairness can be achieved even though one of the two parties is malicious. One of the functions considered by Gordon et al. is exactly the millionaires ’ problem (Yao, FOCS 1982) or, equivalently, the ‘greater-than’ function. Interestingly, Gordon et al. (JACM, 2011) showed that any function over polynomial-size domains which does not contain an “embedded XOR ” can be converted into the greater than function. In the same paper, they also demonstrated feasibility for certain functions that do contain an embedded XOR. In this paper, we revisit both the classes of two-party computation under rational players for the first time. We show that Gordon’s protocols no longer remain fair when the players are rational. Further, we design two protocols, one without embedded XOR (the greater-than function) and the other with embedded XOR, and show that with rational players, our protocols achieve fairness under suitable choice of parameters.

•Jan 1, 2015•0 citations

Fair Computation with Rational Players.

Adam Groce, Jonathan I. Katz

We consider the problem of fair two-party computation, where fairness (informally) means that both parties should learn the correct output. A seminal result of Cleve (STOC 1986) shows that fairness is, in general, impossible to achieve for malicious parties. Here, we treat the parties as rational and seek to understand what can be done. Asharov et al. (Eurocrypt 2011) recently considered this problem and showed impossibility of rational fair computation for a particular function and a particular set of utilities. We observe, however, that in their setting the parties have no incentive to compute the function even in an ideal world where fairness is guaranteed. Revisiting the problem, we show that rational fair computation is possible (for arbitrary functions and utilities) as long as the parties have a strict incentive to compute the function in the ideal world. This gives a new example where game theory can be used to circumvent impossibility results in cryptography.

•Jan 1, 2011•1 citation

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

Cryptography and Secure Two-Party Computation

Gabriel Bender

millionaires, and the pair wishes to determine who has more money. However, neither person wishes to reveal his or her precise wealth to the other. [5] One approach to this problem (dubbed the ideal solution) is for Alice and Bob to find a third party that they both trust. Then Alice tells the third party how much money she has, and Bob follows suit. Once both Alice and Bob have both revealed the necessary information to him, the third party provides both of them with an answer to their question. However, the use of such a trusted third party is not always practical. Therefore, our goal is to simulate the presence of such a third party using cryptography. Secure two-party computation provides a generalization of this problem: Suppose we wish to compute the value of a function F (A, B) where A is an input provided by Alice and B is provided by Bob. Assume furthermore that Alice does not wish to disclose her input to Bob, and that likewise, Bob wishes to conceal his input from Alice. How can they compute F (A, B) together while observing these constraints?

•Jan 1, 2006•0 citations

Complete Fairness in Secure Two-Party Computation.

Steven Gordon, Carmit Hazay, Jonathan I. Katz +1 more

In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable property is fairness which guarantees, informally, that if one party receives its output, then the other party does too. Cleve (STOC 1986) showed that complete fairness cannot be achieved in general without an honest majority. Since then, the accepted folklore has been that nothing non-trivial can be computed with complete fairness in the two-party setting, and the problem has been treated as closed since the late ’80s. In this paper, we demonstrate that this folklore belief is false by showing completely-fair protocols for various non-trivial functions in the two-party setting based on standard cryptographic assumptions. We first show feasibility of obtaining complete fairness when computing any function over polynomial-size domains that does not contain an “embedded XOR”; this class of functions includes boolean AND/OR as well as Yao’s “millionaires ’ problem”. We also demonstrate feasibility for certain functions that do contain an embedded XOR, and prove a lower bound showing that any completely-fair protocol for such functions must have round complexity super-logarithmic in the security parameter. Our results demonstrate that the question of completely-fair secure computation without an honest majority is far from closed.

•Jan 1, 2008•24 citations

Protocols for secure computations

Andrew Chi-Chih Yao

Two millionaires wish to know who is richer; however, they do not want to find out inadvertently any additional information about each other’s wealth. How can they carry out such a conversation? This is a special case of the following general problem. Suppose m people wish to compute the value of a function f(x1, x2, x3, . . . , xm), which is an integer-valued function of m integer variables xi of bounded range. Assume initially person Pi knows the value of xi and no other x’s. Is it possible for them to compute the value of f , by communicating among themselves, without unduly giving away any information about the values of their own variables? The millionaires’ problem corresponds to the case when m = 2 and f(x1, x2) = 1 if x1 < x2, and 0 otherwise. In this paper, we will give precise formulation of this general problem and describe three ways of solving it by use of one-way functions (i.e., functions which are easy to evaluate but hard to invert). These results have applications to secret voting, private querying of database, oblivious negotiation, playing mental poker, etc. We will also discuss the complexity question “How many bits need to be exchanged for the computation”, and describe methods to prevent participants from cheating. Finally, we study the question “What cannot be accomplished with one-way functions”. Before describing these results, we would like to put this work in perspective by first considering a unified view of secure computation in the next section.

•Nov 3, 1982•2,685 citations
A seminal result of Cleve (STOC 1986) showed that fairness, in general, is impossible to achieve in case of two-party computation if one of them is malicious. Gordon et al. (STOC 2008) observed that there exist some functions for which fairness can be achieved even though one of the two parties is malicious. One of the functions considered by Gordon et al. is exactly the millionaires' problem (Yao, FOCS 1982) or, equivalently, the `greater than' function. The problem deals with two millionaires, Alice and Bob, who are interested in finding who amongst them is richer, without revealing their actual wealth to each other. We, for the first time, study this problem in presence of rational players. In particular, we show that Gordon's protocol no longer remains fair when the players are rational. Next, we design a protocol with rational players, that not only achieves fairness, but also achieves correctness and strict Nash equilibrium for natural utilities. We, also for the first time, provide a solution to the quantum version of millionaires' problem with rational players, and it too achieves fairness, correctness and strict Nash equilibrium. Both our classical and quantum protocols follow an unified approach; both uses an untrusted third party (UTP) and exploits the idea of interlocking system between the players, to prevent the deviating party to abort early. In both the protocols, we remove the requirement of the online dealer of Groce et al. (EUROCRYPT 2012).
A seminal result of Cleve (STOC 1986) showed that fairness, in general, is impossible to achieve in case of two-party computation if one of them is malicious. Later, Gordon et al. (STOC 2008) observed that there exist some functions for which fairness can be achieved even though one of the two parties is malicious. One of the functions considered by Gordon et al. is exactly the millionaires ’ problem (Yao, FOCS 1982) or, equivalently, the ‘greater-than’ function. Interestingly, Gordon et al. (JACM, 2011) showed that any function over polynomial-size domains which does not contain an “embedded XOR ” can be converted into the greater than function. In the same paper, they also demonstrated feasibility for certain functions that do contain an embedded XOR. In this paper, we revisit both the classes of two-party computation under rational players for the first time. We show that Gordon’s protocols no longer remain fair when the players are rational. Further, we design two protocols, one without embedded XOR (the greater-than function) and the other with embedded XOR, and show that with rational players, our protocols achieve fairness under suitable choice of parameters.
We consider the problem of fair two-party computation, where fairness (informally) means that both parties should learn the correct output. A seminal result of Cleve (STOC 1986) shows that fairness is, in general, impossible to achieve for malicious parties. Here, we treat the parties as rational and seek to understand what can be done. Asharov et al. (Eurocrypt 2011) recently considered this problem and showed impossibility of rational fair computation for a particular function and a particular set of utilities. We observe, however, that in their setting the parties have no incentive to compute the function even in an ideal world where fairness is guaranteed. Revisiting the problem, we show that rational fair computation is possible (for arbitrary functions and utilities) as long as the parties have a strict incentive to compute the function in the ideal world. This gives a new example where game theory can be used to circumvent impossibility results in cryptography.
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.
millionaires, and the pair wishes to determine who has more money. However, neither person wishes to reveal his or her precise wealth to the other. [5] One approach to this problem (dubbed the ideal solution) is for Alice and Bob to find a third party that they both trust. Then Alice tells the third party how much money she has, and Bob follows suit. Once both Alice and Bob have both revealed the necessary information to him, the third party provides both of them with an answer to their question. However, the use of such a trusted third party is not always practical. Therefore, our goal is to simulate the presence of such a third party using cryptography. Secure two-party computation provides a generalization of this problem: Suppose we wish to compute the value of a function F (A, B) where A is an input provided by Alice and B is provided by Bob. Assume furthermore that Alice does not wish to disclose her input to Bob, and that likewise, Bob wishes to conceal his input from Alice. How can they compute F (A, B) together while observing these constraints?
In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable property is fairness which guarantees, informally, that if one party receives its output, then the other party does too. Cleve (STOC 1986) showed that complete fairness cannot be achieved in general without an honest majority. Since then, the accepted folklore has been that nothing non-trivial can be computed with complete fairness in the two-party setting, and the problem has been treated as closed since the late ’80s. In this paper, we demonstrate that this folklore belief is false by showing completely-fair protocols for various non-trivial functions in the two-party setting based on standard cryptographic assumptions. We first show feasibility of obtaining complete fairness when computing any function over polynomial-size domains that does not contain an “embedded XOR”; this class of functions includes boolean AND/OR as well as Yao’s “millionaires ’ problem”. We also demonstrate feasibility for certain functions that do contain an embedded XOR, and prove a lower bound showing that any completely-fair protocol for such functions must have round complexity super-logarithmic in the security parameter. Our results demonstrate that the question of completely-fair secure computation without an honest majority is far from closed.
Two millionaires wish to know who is richer; however, they do not want to find out inadvertently any additional information about each other’s wealth. How can they carry out such a conversation? This is a special case of the following general problem. Suppose m people wish to compute the value of a function f(x1, x2, x3, . . . , xm), which is an integer-valued function of m integer variables xi of bounded range. Assume initially person Pi knows the value of xi and no other x’s. Is it possible for them to compute the value of f , by communicating among themselves, without unduly giving away any information about the values of their own variables? The millionaires’ problem corresponds to the case when m = 2 and f(x1, x2) = 1 if x1 < x2, and 0 otherwise. In this paper, we will give precise formulation of this general problem and describe three ways of solving it by use of one-way functions (i.e., functions which are easy to evaluate but hard to invert). These results have applications to secret voting, private querying of database, oblivious negotiation, playing mental poker, etc. We will also discuss the complexity question “How many bits need to be exchanged for the computation”, and describe methods to prevent participants from cheating. Finally, we study the question “What cannot be accomplished with one-way functions”. Before describing these results, we would like to put this work in perspective by first considering a unified view of secure computation in the next section.