Yao's Millionaires' problem is a secure multi-party computation problem which was introduced in 1982 by Andrew Yao, a prominent computer scientist and computational theorist. The problem discusses two millionaires, Alice and Bob, who are interested in knowing which of them is richer without revealing their actual wealth.
Contents
This problem is analogous to a more general problem where there are two numbers
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 which are confidential and whose security is important.
Many solutions have been introduced for the problem, among which the first solution, presented by Yao himself, was exponential in time and space. This article presents and explains one possible solution.
The protocol
We will make use of a variant of oblivious transfer, called 1-2 oblivious transfer, in our protocol. In that transfer one bit is transferred in the following way: a sender has two bits
- the receiver doesn't get any information about
S ( 1 − i ) - the value of
i is not exposed to the sender.
Now we will begin with the protocol description. We will indicate Alice's number as
- Alice creates a matrix
K of sized × 2 ofk -bit numbers, wherek is the length of the key in the oblivious transfer protocol. In addition, she chooses two random numbersu andv where0 ≤ u < 2 k andv ≤ k . -
K i j l l -th bit of the number which appears in cellK i j l = 0 indicates the least significant bit). In addition, we denotea i i -th bit of Alice's numbera . For everyi ,1 ≤ i ≤ d Alice does the following actions.- For every bit
j ≥ v she setsK i 1 j K i 2 j - If
a i = 1 letl = 1 otherwise letl = 2 and for everyj , 0 ≤ j ≤ 2 ⋅ i − 1 setK i l j - For
m = 2 ⋅ i setK i l ( m + 1 ) = 1 andK i l m a i - For every
i , 1 ≤ i < d ,S i k -bit number andS d k bits where all bits except the last two are random and the last two are calculated asS d ( k − 1 ) = 1 ⊕ ⨁ j = 1 d − 1 S j ( k − 1 ) ⊕ ⨁ j = 1 d K j 1 ( k − 1 ) S d ( k − 2 ) = 1 ⊕ ⨁ j = 1 d − 1 S j ( k − 2 ) ⊕ ⨁ j = 1 d K j 1 ( k − 2 ) ⨁ is the bitwise XOR operation. - For
l = 1 , 2 setK i j ′ = r o t ( K i l ⊕ S i , u ) . Wherer o t ( x , t ) indicates the bitwise rotation ofx to the left byt bits.
- For every bit
- For every
i ,0 ≤ i ≤ d Bob transfersK i l ′ l = b i + 1 andb i i -th bit ofb . - Alice sends to Bob
N = r o t ( ⨁ j = 1 d S j , u ) . - Bob calculates the bitwise XOR of all the numbers he got in step 3 and
N from step 4. Bob scans the result from left to right until he finds a large sequence of zero bits. Letc be the bit to the right of that sequence (c is non zero). If the bit to the right ofc equals 1 thena ≥ b . otherwisea < b .
Correctness
Bob calculates the final result from
For every i, only one of
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,
-
r o l ( K i ( 1 + b i ) ⊕ S i , u ) for everyi Bob receives one such number andS i - N, This is an XOR of random numbers and therefore reveals no information. The relevant information is revealed only after calculating c and,
- c, The same goes for c. The left part of c is random and the right part is random as well except from 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.
Complexity
The complexity of the protocol is