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
and the goal is to determine whether the inequality
is true or false without revealing the actual values of
and
.
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.[2]
The protocol of Ioannidis and Ananth
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 receiver chooses
, and the sender sends
with the oblivious transfer protocol such that
- the receiver doesn't get any information about
,
- the value of
is not exposed to the sender.
To describe the protocol, Alice's number is indicated as
, Bob's number as
, and it is assumed that the length of their binary representation is less than
for some
. The protocol takes the following steps.
- Alice creates a matrix
of size
of
-bit numbers, where
is the length of the key in the oblivious transfer protocol. In addition, she chooses two random numbers
and
, where
and
.
will be the
-th bit of the number that appears in cell
(where
indicates the least significant bit). In addition,
is denoted as the
-th bit of Alice's number
. For every
,
Alice does the following actions.
- For every bit
she sets
and
to random bits.
- If
, let
, otherwise let
and for every
set
to a random bit.
- For
set
and
to
.
- For every
,
will be a random
-bit number, and
will be another number of
bits where all bits except the last two are random, and the last two are calculated as
and
, where
is the bitwise XOR operation.
- For
set
. Where
indicates the bitwise rotation of
to the left by
bits.
- For every
,
Bob transfers
with the oblivious transfer protocol, where
, and
is the
-th bit of
.
- Alice sends to Bob
.
- Bob calculates the bitwise XOR of all the numbers he got in step 3 and
from step 4. Bob scans the result from left to right until he finds a large sequence of zero bits. Let
be the bit to the right of that sequence (
is non zero). If the bit to the right of
equals 1, then
, otherwise
.
Proof
Correctness
Bob calculates the final result from
, and the result depends on
.
K, and therefore c as well, can be split into 3 parts. 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.
For every i, only one of
has non-zero right part, and it is
if
, and
otherwise. In addition, if
, and
has a non-zero right part, then
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. In the end, if
, then those two leftmost bits will be 11, and Bob will answer that
. If the bits are 10, then
, and he will answer
. If
, 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.
Security
The information Bob sends to Alice is secure because it is sent through oblivious transfer, which is secure.
Bob gets 3 numbers from Alice:
. For every
Bob receives one such number, and
is random, so no secure information is transformed.
- N. This is an XOR of random numbers, and therefore reveals no information. The relevant information is revealed only after calculating c.
- c. The same goes for c. The left part of c is random, and the right part is random as well, except for the two leftmost bits. Deducing any information from those bits requires guessing some other values, and the chance of guessing them correct is very low.
Yao, Andrew C. (November 1982). "Protocols for secure computations". 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982). Vol. 1. pp. 160–164. doi:10.1109/SFCS.1982.88.