A jewellery box and data privacy
A jewellery box and data privacy
A demo of the methods involved in this article is here.
Working with gems
With homomorphic encryption, defined by Craig Gentry in 2010 [here], we can operate on data without ever decrypting it. Craig defined a scenario where Alice had a jewellery box, which she locked with her key, and where her workers could not gain access to the gems contained with it. Then when they wanted to work on the gems, they could do so with special gloves but couldn’t remove them from the box.
With homomorphic encryption allows ciphered values to be moved to wherever they are required, and then processed, without giving away the original data. Data could thus traverse across the Internet and move to places that it is required, and then used to calculate results.
For your tax return we might see:
Sales (Web) &*X43=%
Sales (Print) *65tfd1=
----------
Total Sales 64,532 (=B1+B2)
The sales values are ciphered, but we can still process the addition of the two values. We could also apply subtraction, multiplication and division.
Full homomorphic encryption
One of the first methods to implement full homomorphic encryption is the DGHV (Dijk, Gentry, Halevi and Vaikuntanathan) scheme [paper][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 2×r 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 create an encrypted 2-bit adder function (but which can easily be expanded to adding and multiplying values. The basic schematic is:
The logic is then:
Z0=a0⊕b0
Z0(carry)=a0⋅b0
Z1=a1⊕b1⊕Z0(carry)
Z1(carry)=(a1⋅b1)⊕(a1⋅Z0(carry))⊕(b1⋅Z0(carry))
A sample run is:
r values: 1 7 4 10
q values: 11545 18993 10348 18365
p value: 31517
Input bits
---------------
a0: 0 a1: 0
b0: 0 b1: 0
Encrypted bits
---------------
a0: 363863767 a1: 598602395
b0: 326137924 b1: 578809725
Encrypted values
---------------
Z0_add: 690001691
Z0_carry: 118669773588199708
Z1_add: 118669774765611828
Z1_carry: 139723230046879112813952335
Results
0 0
+ 0 0
-------
0 0 0
The following is an outline of the code which implements a simple version of a 2-bit adder:
import sys
from random import randint
bit_a0 = 0
bit_a1 = 0
bit_b0 = 0
bit_b1 = 0
r1 =randint(1, 10)
r2= randint(1, 10)
r3 =randint(1, 10)
r4 =randint(1, 10)
q1 =randint(10000, 20000)
q2 =randint(10000, 20000)
q3 =randint(10000, 20000)
q4 =randint(10000, 20000)
p =randint(10000, 20000)
c_bit_a0 = q1 * p + 2*r1 +bit_a0
c_bit_a1 = q2 * p + 2*r2 +bit_a1
c_bit_b0 = q3 * p + 2*r3 +bit_b0
c_bit_b1 = q4 * p + 2*r4 +bit_b1
# 2-bit full adder
z0_add = (c_bit_a0 + c_bit_b0)
z0_carry = (c_bit_a0 * c_bit_b0)
z1_add = (c_bit_a1 + c_bit_b1 + z0_carry)
z1_carry = (c_bit_a1 * c_bit_b1) + (c_bit_a1 * z0_carry) + (c_bit_b1 * z0_carry)
print "r values:\t",r1,r2,r3,r4
print "q values:\t",q1,q2,q3,q4
print "p value:\t",p
print "\nEncrypted bits"
print "---------------"
print "a0\t\t",c_bit_a0
print "a1\t\t",c_bit_a1
print "b0\t\t",c_bit_b0
print "b1\t\t",c_bit_b1
print "\nEncrypted values"
print "---------------"
print "Z0_add\t\t",z0_add
print "Z0_carry\t",z0_carry
print "Z1_add\t\t",z1_add
print "Z1_carry\t",z1_carry
#decrypt
z0 = (z0_add % p) % 2
z1 = (z1_add % p) % 2
z2 = (z1_carry % p) % 2
print "\nResults"
print ' ',bit_a1,bit_a0
print'+',
print bit_b1,bit_b0
print '-------'
print z2,z1,z0
And here is a demonstration:
Conclusions
Fully homomorphic encryption offers many advantages over our traditional mathematical operations in computing. As we operate on 1-bit at a time, we need to rebuild our mathematical operations as electronic circuits. As an ex-electronic engineer, I am happy with that.
[1] M. van Dijk, C. Gentry, S. Halevi and V. Vaikuntanathan, "Fully
Homomorphic Encryption over the Integers". Proceedings of Eurocrypt, 2010.