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):
Simple Homomorphic Cipher for Millionaire Problem |
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:
# https://asecuritysite.com/encryption/hom_mill 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.