Yao's Millionaires' Problem

Yao's Millionaires' Problem

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 a \geq b 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[1], was exponential in time and space. This article presents and explains one possible solution.

Contents

Protocol and proof

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 S0 and S1. The receiver chooses i\in\{0,1\} and the sender sends Si with the oblivious transfer protocol such that

  1. the receiver doesn't get any information about S(1 − i),
  2. 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 a and Bob's number as b and assume that the length of their binary representation is less than d for some d\in N. The steps of the protocol are as follows.

  1. Alice creates a matrix K of size d\times2 of k-bit numbers, where k is the length of the key in the oblivious transfer protocol. In addition, she chooses two random numbers u and v where 0 < u < 2k and v \leq k.
  2. Kijl will be the l-th bit of the number which appears in cell Kij (where l = 0 indicates the least significant bit). In addition, we denote ai as the i-th bit of Alice's number a. For every i,  0 \leq i \leq d Alice does the following actions.
    1. For every bit  j \geq v she sets Ki1j and Ki2j to random bits.
    2. If ai = 1 let l = 0 otherwise let l = 1 and for every j, 0 \leq j \leq 2 \cdot i -1 set Kilj to a random bit.
    3. For k=2 \cdot i set Kil(m + 1) = 1 and Kilm to ai.
    4. For every  i, 0 \leq i < d, Si will be a random k-bit number and Sd will be another number of k bits where all bits except the last two are random and the last two are calculated as S_{d(k-1)}=1 \oplus \bigoplus_{j=1}^{d-1}S_{j(k-1)}\oplus \bigoplus_{j=1}^{d}K_{j1(k-1)} and S_{d(k-2)}=1 \oplus \bigoplus_{j=1}^{d-1}S_{j(k-2)}\oplus \bigoplus_{j=1}^{d}K_{j1(k-2)}, where  \bigoplus is the bitwise XOR operation.
    5. For l = 1,2 set  K'_{ij}=rol(K_{il} \oplus S_i,u). Where rol(x,t) indicates the bitwise rotation of x to the left by t bits.
  3. For every i,  0 \leq i \leq d Bob transfers K'il with the oblivious transfer protocol where l = bi + 1 and bi is the i-th bit of b.
  4. Alice sends to Bob N=rol(\bigoplus_{j=1}^d S_j,u).
  5. 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. Let c be the bit to the right of that sequence (c is non zero). If the bit to the right of c equals 1 then a \geq b. otherwise a < b.

Proof

Correctness

Bob calculates the final result from N \oplus \bigoplus_{i=1}^d K'_{i(b_i+1)}=rol(\bigoplus_{i=1}^d K_{i(b_i+1)},u) and the result depends on c=\bigoplus_{i=1}^d K_{i(b_i+1)}. 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 Ki1,Ki2 has non zero right part and it is Ki1 if ai = 1 and Ki2 otherwise. In addition, if i > j and Kil has a non zero right part then K_{il} \oplus K_{jl} has also a non zero right part and the two leftmost bits of this right part will be the same as the one of Ail. 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 ai > bi where i is the highest order bit in which a and b differ. In the end, if ai > bi then those two leftmost bits will be 11 and Bob will answer that  a \geq b . If the bits are 10 then ai < bi and he will answer a<b. If a=b 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,

  1. rol(K_{i(1+b_i)} \oplus S_i ,u) for every i Bob receives one such number and Si is random so no secure information is transformed,
  2. N, This is an XOR of random numbers and therefore reveals no information. The relevant information is revealed only after calculating c and,
  3. 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 O(d2). 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 O(d2). The communication part takes also O(d2). Therefore the complexity of the protocol is O(d2).

Notes

See also


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • china — /chuy neuh/, n. 1. a translucent ceramic material, biscuit fired at a high temperature, its glaze fired at a low temperature. 2. any porcelain ware. 3. plates, cups, saucers, etc., collectively. 4. figurines made of porcelain or ceramic material …   Universalium

  • China — /chuy neuh/, n. 1. People s Republic of, a country in E Asia. 1,221,591,778; 3,691,502 sq. mi. (9,560,990 sq. km). Cap.: Beijing. 2. Republic of. Also called Nationalist China. a republic consisting mainly of the island of Taiwan off the SE coast …   Universalium

  • Secure multi-party computation — (also known as secure computation or multi party computation (MPC)) is a sub field of cryptography. The goal of methods for secure multi party computation is to enable parties to jointly compute a function over their inputs, while at the same… …   Wikipedia

  • Socialist millionaire — The Socialist Millionaire Problemcite conference author = M. Jakobsson, M. Yung title = Proving without knowing: On oblivious, agnostic and blindfolded provers. booktitle = Advances in Cryptology CRYPTO 96, volume 1109 of Lecture Notes in… …   Wikipedia

  • Corruption in the People's Republic of China — Political corruption Corruption Perceptions Index, 2010 …   Wikipedia

  • 2008 Sichuan earthquake — 2008 Earthquake 2008 Wenchuan Earthquake …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”