9
$\begingroup$

I'm currently reading about Yao' Millionaire Problem: http://research.cs.wisc.edu/areas/sec/yao1982-ocr.pdf

Alice and Bob want to know which of them is richer. Let $j \in \{1, \cdots 10\}$ be Bobs fortune, and $i$ Alice's. They share a public-private key pair where $E_A$ is the encryption with Alice's public key and $D_A$ the corresponding decryption function.

Here is Yao's roadmap:

  1. Bob picks a random $N$-bit integer, and computes privately the value of $E_A(x)$; call the result $k$.
  2. Bob sends Alice the number $k-j+ 1$.
  3. Alice computes privately the values of $y_u=D_A(k-j+u)$ for $u= 1,2, \cdots,10$.
  4. Alice generates a random prime $p$ of $N/2$ bits, and computes the values $z_u=y_u \mod p$ for all $u$ ; if all $z_u$ differ by at least 2 in the $\bmod p$ sense, stop; otherwise generates another random prime and repeat the process until all $z_u$ differ by at least 2 ; let $p, z_u$ denote this final set of numbers;
  5. Alice sends the prime $p$ and the following 10 numbers to B: $z_1, z_2, \cdots , z_i$ followed by $z_{i}+ 1, z_{i+1}+1 , \cdots , z_{10}+ 1$ the above numbers should be interpreted in the $\bmod p$ sense.
  6. Bob looks at the $j$-th number (not counting $p$ ) sent from Alice, and decides that $i \ge j$ if it is equal to $x \bmod p$, and $i < j$ otherwise.

I understand everything, but I'm at loss at step 4. Why do the $z_u$ have to differ by at least 2? What can Bob deduce from Alice's List, if that condition is not fulfilled?

Added 8.5.16: I found that Bruce Schneier mentions that protocol in "Applied Cryptography". He writes: "All the verification ... is to guarantee that no number apperas twice in the sequence ... Otherwise, if $z_a = z_b$, Alice knows that $a \le j < b$'' (Schneier interchanged Alice and Bob and $i$ with $j$). But he does not explain, why the initiator of the protocol can deduce that.

One more idea: Maybe the condition is not needed for all asymmetric encryption schemes but only for RSA (the only one at that time?). But I cannot show that either.

Added 9.6.16

One more thought: Let's assume, Bob gets from Alice a list, that looks like that: [$w_i$] = [11,7,6,22,33,44,55,66,77,88], then he can argue as follows:

  1. Opps, the list contains two elements having distance one (7,6)

  2. Alice follws the protocol, so the $z_i$ differ by at least 2

  3. So Alice, when calculating the $w_i$ must have incremented the smaller one of the corresponding $z$s

  4. So [$z_i$] must have been [11,7,5,21,32,43,54,65,76,87]

  5. So Alice's fortune equals 2

So I think, the distance condition is not only useless but dangerous because it removes entropy from the result set (an adds information).

$\endgroup$
  • $\begingroup$ Welcome to crypto-SE. A quick note, tho: If you use the latex math formulas (see markdown), formulas are much more readable. And you should try to have all the necessary information in your post, e.g. "$E_A$ denotes encryption with Alice public key" (which wasn't obvious on the first glance; and after checking the paper, that is just in the paragraph before your quotation). $\endgroup$ – tylo May 3 '16 at 9:09
  • $\begingroup$ Ups. While reading my posting again, I found, that I cited it correctly from Yao, but I think, there's a mistake in Step 5. It Must be '': ... and the following 10 numbers to B: $z_1, z_2 \cdots,z_i$ followed by $z_{i+1}+1 \cdots, ,z_{10}+1$ ...'' ($z_i$ not duplicated). $\endgroup$ – Calculatrix May 3 '16 at 9:38
  • 1
    $\begingroup$ I'm not familiar with this protocol, but looking at step 5, it seems likely that the reason why the $z$ values must differ by at least two is to avoid the possibility that $z_a = z_b+1$ for some $a$ and $b$, which could cause two of the numbers transmitted in step 5 to be identical. I'm not sure why that would actually be a problem, though. $\endgroup$ – Ilmari Karonen May 3 '16 at 11:36
  • 1
    $\begingroup$ @Aventinus: No, its not a homework. I'm only trying (and still failing) to understand that step in the protocol. Yeah i'ts really ancient, but cool. $\endgroup$ – Calculatrix May 6 '16 at 16:39
  • 3
    $\begingroup$ I would recommend against spending much time studying Yao's Millionaires' Problem, and especially Yao's original solution, which is mostly of historical interest. $\endgroup$ – fkraiem Jun 9 '16 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.