Simple Homomorphic Cipher XOR between two integers

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).

The logic is check by taking each bit and performing an EX-OR function on it

Code

The following is an outline:

import sys
from random import randint
import bitarray



def to_bin(num):
	binary = []
	while num != 0:
    		bit = num % 2
    		binary.insert(0, bit)
    		num = num / 2
	return binary



def rev(text):
    lst=[]
    for i in range(0,len(text)):
        lst.append(text[(len(text)-1)-i])
    return lst


val1=128
val2=129

if (len(sys.argv)>1):
       val1=int(sys.argv[1])
if (len(sys.argv)>2):
       val2=int(sys.argv[2])

bits1=rev(to_bin(val1))
bits2=rev(to_bin(val2))

print bits1
print bits2

print "Value 1: ",val1, "Value 2: ",val2

c_bits1 = [0 for i in xrange(len(bits1))]
c_bits2 = [0 for i in xrange(len(bits2))]

	
p =randint(100000, 200000)

no_bits=len(bits1)

if (len(bits2)<no_bits):
	no_bits = len(bits2)

print "Cipher bits 1:"
print "Bit\tCipher\t\tq\t\tr"
for i in range(0,no_bits):
	q=randint(5000000, 9000000)
	r=randint(1,200)
	c_bits1[i] =  q * p + 2*r +int(bits1[i])
	print bits1[i], "\t",c_bits1[i],"\t",q,"\t",r
	if (2*r > p/2): 
		print 'Error'


print "Cipher bits 2:"
print "Bit\tCipher\t\tq\t\tr"
for i in range(0,no_bits):
	q=randint(5000000, 9000000)
	r=randint(1,200)
	c_bits2[i] =  q * p + 2*r +int(bits2[i])
	print bits2[i], "\t",c_bits2[i],"\t",q,"\t",r
	if (2*r > p/2): 
		print 'Error'

print 
print "p value:\t",p
print "XOR values of bits"
print "Bit\tXOR\tCipher"
for i in range(0,no_bits):
	cbit = c_bits1[i] + c_bits2[i]
	print i,"\t",(cbit % p) % 2,"\t",cbit

Example

In the following we create 16 cipher value bits and then make a calculation, and then decipher with the p value:

Value 1:  221 Value 2:  220
Cipher bits 1:
Bit	Cipher		q		r
1 	9231474401152 	55562089 	34
1 	11465244887041 	69006632 	68
0 	9036397221123 	54387965 	134
1 	14708693516595 	88528192 	185
1 	9317891111264 	56082211 	123
1 	14359678149915 	86427550 	32
0 	13863684329325 	83442279 	156
1 	8605148726252 	51792381 	122
Cipher bits 2:
Bit	Cipher		q		r
1 	14113275170779 	84944508 	51
1 	8390745991410 	50501941 	41
0 	14097072515446 	84846988 	105
1 	11424420741678 	68760921 	145
1 	13789188832805 	82993908 	164
1 	9395499371664 	56549317 	32
0 	11633635203886 	70020134 	94
0 	14821940640818 	89209800 	109

p value:	166147
XOR values of bits
Bit	XOR	Cipher
0 	0 	23344749571931
1 	0 	19855990878451
2 	0 	23133469736569
3 	0 	26133114258273
4 	0 	23107079944069
5 	0 	23755177521579
6 	0 	25497319533211
7 	1 	23427089367070

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.