[Back] In Millionaire's Problem, we can determine which of two millionaires has the most money, without them actually giving away the amount of money they have:

## Millionaire's Problem |

## Method

The method involves us using RSA encryption. For this I've used Example 4 from here:

e=79 d=1019 N=3337

and select a prime number:

p=631

We define I as Bob's millions, and J as Alice's millions:

J =4 I = 5

Next we select a random number U:

U=randint(0,2000)

And compute the C value (which is the RSA encryption process):

\(C=U^e \mod N\)

Now Alice calculates:

C - J + 1

She shares this with Bob, and Bob calculates 10 values:

\(Z_1 = (((\text{valforalice}+1)^d) \mod N) \mod p \\ Z_2 = (((\text{valforalice}+2)^d) \mod N) \mod p \\ ..\\ Z_{10} = (((\text{valforalice}+2)^d) \mod N) \mod p \\ \)

Bob then takes these values, and if for the i-th value, and the rest, he will one he will add one onto the value. These are then sent back to Alice.

Alice now computes:

\(G = U \mod p\)

If the j-th value is the same as G, Alice has more money or the same, else Bob has more money.

## Coding

import sys from random import randint J = 4 I = 5 e=79 d=1019 N=3337 primes = [601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997] val=randint(0,len(primes)) p=primes[val] U=randint(0,2000) C=(U**e) % N print 'Bob has',I,'millions' print 'Alice has',J,'millions' print '\ne=',e,'d=',d,'N=',N,'p=',p print '\nRandom Value U is:\t',U print 'C value is (U^e %N):\t',C val_for_alice = C - J + 1 print "Alice shares this value (C-J-1):",val_for_alice Z=[] for x in range(0,10): val = (((val_for_alice+x)**d) % N) % p if (x>(I-1)): Z.append(val+1) else: Z.append(val) G = U % p print "\nG value is",G print "Z values are:", for x in range(0,10): print Z[x], print '\n\nAlice checks U(',U,') against the ',J,'th value (',Z[J-1],')' if (G==Z[J-1]): print "\nSame. Bob has more money or the same" else: print "\nDiffer. Alice has more money"

And a sample run:

Bob has 3 millions Alice has 4 millions e= 79 d= 1019 N= 3337 p= 887 Random Value U is: 1078 C value is (U^e %N): 3273 Alice shares this value (C-J-1): 3270 G value is 191 Z values are: 256 164 623 192 122 243 594 591 147 728 Alice checks U( 1078 ) against the 4 th value ( 192 ) Differ. Alice has more money