6 Comparing Ages

The following protocol from Yao is based on a Public-Key Cryptosystem. it enables two people to find out who of both is older, without revealing their ages.
Let Alice be i, Bob j years old, besides set 0 < i, j <= 100.
First Alice must publish her public key E_A.

The protocol goes:

(i)	Bob randomly chooses a large number x, whose number of bits has been set in advance (1), and determines EA(x) = k. (2)
(ii)	Bob sends Alice the number k - j. (3)
(iii)	Alice determines yu = DA(k - j + u), u = 1,2,...,100. (4) Here yu != 0 must hold for all u; otherwise the protocol must be restarted with a new x. Alice chooses a large prime p (5), whose number of bits has also been set in advance, namely a bit smaller than the amount of bits of x. Thereof, Alice calculates zu = yu mod p, u = 1,2,...,100. (6) Now zu < p holds for all zu. If |zu-zu'| > 1 for u != u' and 0 < zu < p-1, Alice has chosen a suitable p, otherwise the calculation must be repeated with a different p.
(iv)	Alice sends Bob the sequence of the numbers z1, z2,..., zi, zi+1+1, zi+2+1,..., z100+1, p. (7)
(v)	Bob tests if fj = x mod p for the j-th number fj of the sequence. (8) If this is the case, Bob concludes that i >= j. Otherwise i < j is true.
(vi)	Bob tells Alice about his conclusion. (9)

The red numbers mark the steps of the sample applet. For simplifying the presentation it is only suited for people between 20 and 30.
As the Public-Key system RSA was chosen (the preselected parameters may be overwritten, but are not checked for correctness). x has 12, p has 11 bits.

Start applet in new window

7 LFKN protocol