Simple Homomorphic Cipher for Millionaire Problem

[Back] 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. 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):

Theory

The code uses the DGHV (Dijk, Gentry, Halevi and Vaikuntanathan) scheme [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 \times q + 2 \times 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.

With this function we can add (XOR) and multiply (AND).

In this example we will create a True Table for Bob (\(b_0b_1\) and Alice (\(a_1a_0\)). 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):

\(G=a_0 \bar{b_1} \bar{b_0} + a_1 \bar{b_1} + a_1 a_0 \bar{b_0} \)

\(E=\bar{a_1} \bar{a_0} \bar {b_1} \bar{b_0} + \bar{a_1} a_0 \bar {b_1} b_0 + + a_1 a_0 b_1 b_0 + + a_1 \bar{a_0} b_1 \bar{b_0} \)

\(L=\bar{a_1} b_1 + \bar{a_0} b_1 b_0 + \bar{a_1} \bar{a_0} b_0\)

Code

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

Presentation

Here is a presentation on the method used:

Reference

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

Simple Homomorphic Cipher for Millionaire Problem

Parameters

Theory

Code

Presentation

Reference