Yao's Millionaires' Problem
Encyclopedia
Yao's Millionaires' problem is a secure multiparty communication problem which was introduced 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.
This problem is analogous to a more general problem where there are two numbers a and b and the goal is to solve the inequality
without revealing the actual values of a and b.
The Millionaires' Problem is an example of Secure multi-party computation, which is an important problem in cryptography
and 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.
, called 1-2 oblivious transfer, in our protocol
. 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
Now we will begin with the protocol description. We will indicate Alice's number as
and Bob's number as 
and assume that the length of their binary representation is less than 
for some 
. The steps of the protocol are as follows.
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 there is a sequence of zeros what separate 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 which are not random are the two leftmost, Exactly the bits which 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 a
Bob gets 3 numbers from Alice,
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 complexity of those operations is 
. The communication part takes also 
. Therefore the complexity of the protocol is 
Andrew Yao
Andrew Chi-Chih Yao is a prominent computer scientist and computational theorist. Yao used the minimax theorem to prove what is now known as Yao's Principle.Yao was born in Shanghai, China...
, 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.
This problem is analogous to a more general problem where there are two numbers a and b and the goal is to solve the inequality
without revealing the actual values of a and b.The Millionaires' Problem is an example of Secure multi-party computation, which is an important problem in cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
and the solution of which is used in e-commerce and data mining
Data mining
Data mining , a relatively young and interdisciplinary field of computer science is the process of discovering new patterns from large data sets involving methods at the intersection of artificial intelligence, machine learning, statistics and database systems...
. 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 transferOblivious transfer
In cryptography, an oblivious transfer protocol is a type of protocol in which a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious as to what piece has been transferred....
, called 1-2 oblivious transfer, in our protocol
Cryptographic protocol
A security protocol is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods.A protocol describes how the algorithms should be used...
. In that transfer one bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
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.
Now we will begin with the protocol description. We will indicate Alice's number as
and Bob's number as and assume that the length of their binary representation is less than for some . The steps of the protocol are as follows.
- 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 which appears in cell 
(where 
indicates the least significant bitLeast significant bitIn computing, the least significant bit is the bit position in a binary integer giving the units value, that is, determining whether the number is even or odd. The lsb is sometimes referred to as the right-most bit, due to the convention in positional notation of writing less significant digits...
). In addition, we denote
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 bitwiseBitwise operationA bitwise operation operates on one or more bit patterns or binary numerals at the level of their individual bits. This is used directly at the digital hardware level as well as in microcode, machine code and certain kinds of high level languages...
XOR operation. - For
set 
. Where 
indicates the bitwise rotation of 
to the left by 
bits.
- For every bit
- 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 
.
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 there is a sequence of zeros what separate 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 which are not random are the two leftmost, Exactly the bits which 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 aSecurity
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 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 complexityComplexity
In general usage, complexity tends to be used to characterize something with many parts in intricate arrangement. The study of these complex linkages is the main goal of complex systems theory. In science there are at this time a number of approaches to characterizing complexity, many of which are...
of the protocol
Cryptographic protocol
A security protocol is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods.A protocol describes how the algorithms should be used...
is
. Alice constructs d length number for each bit of a and Bob calculates XOR d times of d length numbers. The complexity of those operations is . The communication part takes also . Therefore the complexity of the protocol is See also
- CryptographyCryptographyCryptography is the practice and study of techniques for secure communication in the presence of third parties...
- Secure multi-party computation
- RSA
- Socialist millionaireSocialist millionaireThe Socialist Millionaire Problem is one in which two millionaires want to determine if their wealth is equal, without disclosing any information about their riches to each other...
, a variant in which the millionaires wish to determine whether their fortunes are equal.