Bob and Alice Are Now Rich, But Who Has Most Money?

Bob and Alice Are Now Rich, But Who Has Most Money?

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.

In this case, we will split their well into $1 million (00), $2 million (01), $3 million (10), and $4 billion (11). We can then create a K-map for “greater than” and “equal to”:

The logic then becomes:

This logic is then implemented in Python as:

g = c_bit_a_0*inv(c_bit_b_1)*inv(c_bit_b_0) + c_bit_a_1*inv(c_bit_b_1) \
 + c_bit_a_1*c_bit_a_0*inv(c_bit_b_0)
e = inv(c_bit_a_1)*inv(c_bit_a_0)*inv(c_bit_b_1)*inv(c_bit_b_0)+ \
 inv(c_bit_a_1)*(c_bit_a_0)*inv(c_bit_b_1)*c_bit_b_0+ \
 (c_bit_a_1)*(c_bit_a_0)*(c_bit_b_1)*(c_bit_b_0)+ \
 (c_bit_a_1)*inv(c_bit_a_0)*(c_bit_b_1)*inv(c_bit_b_0)

l=inv(c_bit_a_1)*c_bit_b_1 + inv(c_bit_a_0)*c_bit_b_1*c_bit_b_0 \
 + inv(c_bit_a_1)*inv(c_bit_a_0)*c_bit_b_0

Now, in order to preserve the values of Bob and Alice’s wealth, we create cipher values of their values. The code we will use uses the DGHV (Dijk, Gentry, Halevi and Vaikuntanathan) scheme [paper] and which is a somewhat homomorphic encryption scheme [1]. First, we get a random number (p) and two random numbers (q and r), and then encrypt a single bit (m) with:

This will take each bit and cipher it. It will then not be possible for the circuit to know the actual values of the bits being used. We can then process with our logic, and then decipher the end results with:

Only if we know the secret — p — can we decipher the results. You can try the program here, and here is the Python code:

import sys
from random import randint

a_0 = 1
a_1 = 0
b_0 = 0
b_1 = 0

def inv(val):
	return(val ^ 1)
	
r1 =randint(1, 5)
r2= randint(1, 5)
r3 =randint(1, 5)
r4 =randint(1, 5)

q1 =randint(50000, 60000)
q2 =randint(50000, 60000)
q3 =randint(50000, 60000)
q4 =randint(50000, 60000)

p =randint(10000, 20000)

c_bit_a_0 =  q1 * p + 2*r1 +a_0
c_bit_a_1 =  q2 * p + 2*r2 +a_1 
c_bit_b_0 =  q3 * p + 2*r3 +b_0 
c_bit_b_1=  q4 * p + 2*r4 +b_1

# Truth table
g = c_bit_a_0*inv(c_bit_b_1)*inv(c_bit_b_0) + c_bit_a_1*inv(c_bit_b_1)  + c_bit_a_1*c_bit_a_0*inv(c_bit_b_0)
e = inv(c_bit_a_1)*inv(c_bit_a_0)*inv(c_bit_b_1)*inv(c_bit_b_0)+ \
inv(c_bit_a_1)*(c_bit_a_0)*inv(c_bit_b_1)*c_bit_b_0+ \
(c_bit_a_1)*(c_bit_a_0)*(c_bit_b_1)*(c_bit_b_0)+ \
(c_bit_a_1)*inv(c_bit_a_0)*(c_bit_b_1)*inv(c_bit_b_0)

l=inv(c_bit_a_1)*c_bit_b_1 + inv(c_bit_a_0)*c_bit_b_1*c_bit_b_0+ inv(c_bit_a_1)*inv(c_bit_a_0)*c_bit_b_0

			
print "r values:\t",r1,r2,r3,r4
print "q values:\t",q1,q2,q3,q4
print "p value:\t",p

print "\nInput bits"
print "---------------"
print "a_1:\t",a_1, "\ta_0:\t",a_0
print "b_1:\t",b_1, "\tb_0:\t",b_0

print "\nCipher bits"
print "---------------"
print "c_a_1:\t",c_bit_a_1, "\tc_a_0:\t",c_bit_a_0
print "c_b_1:\t",c_bit_b_1, "\tc_b_0:\t",c_bit_b_0

print "\nCipher result"
print "---------------"

#decrypt
result_greater = (g % p) % 2
result_equal = (e % p) % 2
result_less = (l % p) % 2

print "\nResults"
print "Greater than:\t",result_greater
print "Equal:\t\t",result_equal
print "Less than:\t",result_less

Here is the problem [here].