Yao's Millionaires' problem is a secure multi-party computation problem introduced in 1982 by computer scientist and computational theorist Andrew Yao.
The problem discusses two millionaires, Alice and Bob, who are interested in knowing which of them is richer without revealing their actual wealth.
This problem is analogous to a more general problem where there are two numbers
and the goal is to determine whether the inequality
is true or false without revealing the actual values of
The Millionaires' problem is an important problem in cryptography, the solution of which is used in e-commerce and data mining.
Commercial applications sometimes have to compare numbers that are confidential and whose security is important.
Many solutions have been introduced for the problem, including physical solutions based on cards.
[1] The first solution, presented by Yao, is exponential in time and space.
be a binary string of length n. Denote 0-encoding of s as
Then, the protocol[3] is based on the following claim: The protocol leverages this idea into a practical solution to Yao's Millionaires' problem by performing a private set intersection between
The protocol[4] uses a variant of oblivious transfer, called 1-2 oblivious transfer.
In that transfer one bit is transferred in the following way: a sender has two bits
, and the sender sends
with the oblivious transfer protocol such that To describe the protocol, Alice's number is indicated as
, and it is assumed that the length of their binary representation is less than
The protocol takes the following steps.
Bob calculates the final result from
The left part doesn't affect the result.
The right part has all the important information, and in the middle is a sequence of zeros that separates those two parts.
The length of each partition of c is linked to the security scheme.
has also a non-zero right part, and the two leftmost bits of this right part will be the same as the one of
As a result, the right part of c is a function of the entries Bob transferred correspond to the unique bits in a and b, and the only bits in the right part in c that are not random are the two leftmost, exactly the bits that determines the result of
, where i is the highest-order bit in which a and b differ.
, then those two leftmost bits will be 11, and Bob will answer that
, then there will be no right part in c, and in this case the two leftmost bits in c will be 11, and will indicate the result.
The information Bob sends to Alice is secure because it is sent through oblivious transfer, which is secure.
Bob gets 3 numbers from Alice: The complexity of the protocol is
Alice constructs d-length number for each bit of a, and Bob calculates XOR d times of d-length numbers.
The communication part takes also