The Millionaire’s Problem In A World Where Bob and Alice Trust No-one

The Millionaire’s Problem In A World Where Bob and Alice Trust No-one

Circuits, bits and secret processing

Bob and Alice are now millionaires, and they want to find out who has more money, but don’t want to tell each other how much they are worth. This is defined as the Millionaire’s Problem, and we can solve it using encrypted cipher values and then feeding this into a circuit and getting a result for Greater than, Equal to, and Less than.

The problem can be achieved by zero-knowledge proof, but let’s look at homomorphic encryption to solve the problem. For this we will use the method defined by DGHV (Dijk, Gentry, Halevi and Vaikuntanathan) [paper] and which is a fully 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:

c=p×q+2×r+m

In this case p will be our secret key.

If 2r is smaller than p/2, we cipher with mod p we get:

d=(c mod p)mod 2

We have basically added noise to the value with the q and r values.

Try example here.

Every logical function can be created with add (XOR) and multiply (AND). In this case we will take four values for the number of millions (00–1 million, 01–2 million, 10–3 million, and 11–4 million). We now need to create the circuit, and which we will create a truth table for Bob (b₀b₁) and Alice (a₁a₀). In this case we will return a 1 if Bob is older, and a 0 is he is not:

The logic is then (G — greater than, E — equal to, and L — less than):

The following is an outline:

import sys
from random import randint

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

if (len(sys.argv)>1):
       a_0=int(sys.argv[1])
if (len(sys.argv)>1):
        a_1=int(sys.argv[2])
if (len(sys.argv)>1):
        b_0=int(sys.argv[3])
if (len(sys.argv)>1):
        b_1=int(sys.argv[4])

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

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

p =randint(1000000, 2000000)

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

In this case we will take four values for the number of millions (00–1 million, 01–2 million, 10–3 million, and 11–4 million):

r values: 8 3 4 8
q values: 53184 55733 50821 55217
p value: 2971171

Input bits
 — — — — — — — -
a_1: 0 a_0: 0
b_1: 0 b_0: 0

Cipher bits
 — — — — — — — -
c_a_1: 165592273349 c_a_0: 158018758480
c_b_1: 164059149123 c_b_0: 150997881399

Cipher result
 — — — — — — — -

Results
Greater than: 0
Equal: 1
Less than: 0

We can see that Bob and Alice can create these cipher bits, and then use the cipher circuit to find out who has more money, but not reveal how much money each of them have. Try example here.

Conclusions

The millionaire’s problem is one of the most fundamental problems within zero-knowledge proof, where Bob and Alice do not trust anyone, but can still prove something, without revealing the core data. We have solved in, in this case, with homomorphic encryption, and which could be used in real life applications of operating on cipher values. This would be a world in which we could prove things — such as your password — without actually revealing it.

References

[1] M. van Dijk, C. Gentry, S. Halevi and V. Vaikuntanathan, "Fully Homomorphic Encryption over the Integers". Proceedings of Eurocrypt 2010.