How does Alice tell if she had more money than Bob, but where she can’t tell how many millions Bob…

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 =5

Alice selects a random number U:

U=randint(0,2**16)

She then computes the C value (which is the RSA encryption process):

C=U^e (mod N)

Now she calculates:

m=C - J + 1

She shares this with Bob. He then takes this value, and he adds one onto each one and generates 10 values:

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

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

…

Z10=(((m+2)^d) mod N ) mod p

He sends these to Alice, and 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
from Crypto.Util.number import getPrime

import Crypto
import libnum


J = 4
I = 5


bits=120

if (len(sys.argv)>1):
	I=int(sys.argv[1])
if (len(sys.argv)>2):
	J=int(sys.argv[2])
if (len(sys.argv)>3):
	bits=int(sys.argv[3])


p = getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
q = getPrime(bits, randfunc=Crypto.Random.get_random_bytes)

N = p*q
PHI=(p-1)*(q-1)

e=65537
d=libnum.invmod(e,PHI)

p=getPrime(bits, randfunc=Crypto.Random.get_random_bytes)

U=randint(0,2**32)

C=pow(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 = (pow(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("\nBob has more money or the same")
else: print("\nAlice has more money")

And a sample run [here]:

Bob has 2 millions
Alice has 5 millions
Number of bits in primes: 64

e= 65537 d= 169478917908710893076953484803853045729 
N= 179112749838469744586204437449540413039 z= 13150293424160624497

Random Value U is:  2109553539
C value is (U^e %N):  119811050022181764387313538039699231779
Alice shares this value (C-J-1): 119811050022181764387313538039699231775

G value is 2109553539
Z values are:
6037212376965562891 7015309241927881178 11707508124397142878 9806378449777342779 2109553540 739799036603140480 9174291558988026553 175367038966361488 1282179642215612005 487555406965192223

Alice checks U( 2109553539 ) against the  5 th value ( 2109553540 )

Alice has more money

Here is a more formal definition [here]:

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.

So here is an example: