This is a simple abstraction of homomorphic cipher for a Full Adder. In this case we are adding a, b and Cin:
Simple Homomorphic Cipher for a Full Adder |
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 (OR) and multiply (AND).
In this example we create an encrypted full adder function. The basic schematic for a half-adder is:
A full adder is then created from the half-adder with:
For a Half-adder (HA), the logic is:
\(Sum=\bar{a}\cdot b + a \cdot \bar{b} \)
\(Carry=a + b \)
For a Full-adder (FA) we have inputs of a, b and \(C_{in}\), and which gives Sum and \(C_{out}\):
\(sum_1,c_1=HA(a,b)\)
\(Sum,c_2=HA(sum_1,cin)\)
\(C_{out}= c_1 + c_2\)
Code
The following is an outline and where I have used XOR, NOT, AND, HA and FA functions:
import sys from random import randint def XOR(a,b): return ( (NOT(a)*b) + (a*NOT(b))) def NOT(val): return(val ^ 1) def AND(a,b): return(a*b) def OR(a,b): return(a+b) def HA(bit1,bit2): sum=XOR(bit1,bit2) carryout=AND(bit1,bit2) return sum,carryout def FA(bit1,bit2,cin): sum1,c1=HA(bit1,bit2) sum,c2=HA(sum1,cin) carryout=OR(c1,c2) return sum,carryout def cipher(bit,p): q=randint(50000000, 90000000) r=randint(1,200) return( q * p + 2*r +int(bit)),q,r bit1=0 bit2=0 carryin=0 if (len(sys.argv)>1): bit1=str(sys.argv[1]) if (len(sys.argv)>2): bit2=str(sys.argv[2]) if (len(sys.argv)>3): carryin=str(sys.argv[3]) p =randint(30000000, 60000000)*2+1 print("Bit\tVal\tCipher\t\t\tq\t\tr") print("------------------------------------------------") c_bits1,q,r=cipher(bit1,p) print("Bit1\t",bit1, "\t",c_bits1,"\t",q,"\t",r) c_bits2,q,r=cipher(bit2,p) print("Bit2\t",bit2, "\t",c_bits2,"\t",q,"\t",r) c_carryin,q,r=cipher(carryin,p) print("Cin\t",carryin, "\t",c_carryin,"\t",q,"\t",r) c_sum,c_carryout=FA(c_bits1,c_bits2,c_carryin) print() print("Sum (cipher):\t",c_sum) print("Cout (cipher):\t",c_carryout) print("p value:\t",p) #decrypt sum = (c_sum % p) % 2 carryout = (c_carryout % p) % 2 print("\nResults") print("Sum:\t\t",sum) print("Carryout:\t",carryout)
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.