How does Alice tell if he had more money than Bob, but where she can’t tell how many millions Bob has?
Defining a world where you 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 Yao’s millionaire 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. Bob first selects two prime numbers (p and q) and computes the modulus:
N=p×q
He will use a typical encryption key (e) of:
e=65537
He then computes PHI with:
PHI = (p-1)(q-1)
And then computes the decryption key (d) as:
d=e^{−1} (mod PHI)
We then define I as Bob’s millions, and J as Alice’s millions:
J =4
I =5Alice selects a random number U:
U=randint(0,2**16)
