The Millionaire’s Problem

With all the security breaches going around, Bob and Alice are now wealthy but have fallen out. In fact, they don’t trust each other…

The Millionaire’s Problem — In a World Where You Just Can’t Trust Anyone

With all the security breaches going around, Bob and Alice are now wealthy but have fallen out. In fact, they don’t trust each other anymore and don’t even trust Trent to audit their accounts. So how can Bob and Alice compare their wealth, and find out who has more, without them knowing how wealthy each of them is? This is known as the millionaire’s problem and is well-known as a problem in processing things without any trusted third party. So, let’s create a method to solve it.

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:

Z1=(((valforalice+1)^d) mod N) mod p

Z2=(((valforalice+2)^d) mod N) mod p

…

Z10=(((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.The following is some Python code [here]:

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 [here]:

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

Conclusions

The method we have defined here is Yao’s millionaire problem. In real-life there are many things that we need to compare, but also where we cannot trust anyone to compare for us.