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:", end=' ') for x in range(0,10): print(Z[x], end=' ') 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