# Yaos Millionaire Problem: Why distance >= 2?

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).

• 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). – tylo May 3 '16 at 9:09
• 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). – Calculatrix May 3 '16 at 9:38
• 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. – Ilmari Karonen May 3 '16 at 11:36
• @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. – Calculatrix May 6 '16 at 16:39
• I would recommend against spending much time studying Yao's Millionaires' Problem, and especially Yao's original solution, which is mostly of historical interest. – fkraiem Jun 9 '16 at 8:07