This page uses the DGHV (Dijk, Gentry, Halevi and Vaikuntanathan) homomorphic encryption scheme, and where we cipher bits with noise, and then use a circuit to implement the required logic. It is a simple abstraction of Homomorphic Cipher - 4-bit adder/subtractor. In this case we are adding a and b or subtracting b from a, where a and b can range from 0 to 15. The coding in this example uses a circuit where M=0 will perform an addition, and M=1 will perform a subtraction:
Homomorphic Cipher - 4-bit adder/subtractor |
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 \(\pmod p\) we get:
\(d = (c \pmod p) \pmod 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 4-bit add function:
Figure [Ref: here]
If we select M=0, we have an adder, whereas M=1 gives a subtractor circuit. We create a subtractor circuit as we take the value B, and then convert to 2's complement (invert the bits and add 1). The EX-OR gate with M=1 as an input is used to invert the bits.
A half adder is created with:
A full adder is created 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 tobits(val): l = [0]*(8) l[0]=val & 0x1 l[1]=(val & 0x2)>>1 l[2]=(val & 0x4)>>2 l[3]=(val & 0x8)>>3 return l 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(50000, 90000) r=randint(1,200) return( q * p + 2*r +int(bit)),q,r val1=13 val2=10 cin=1 v1=[] v2=[] v1=tobits(val1) v2=tobits(val2) p =randint(3e23, 6e23)*2+1 c_carryin,q,r=cipher(cin,p) cval1b0,q,r=cipher(v1[0],p) cval2b0,q,r=cipher(XOR(v2[0],c_carryin),p) cval1b1,q,r=cipher(v1[1],p) cval2b1,q,r=cipher(XOR(v2[1],c_carryin),p) cval1b2,q,r=cipher(v1[2],p) cval2b2,q,r=cipher(XOR(v2[2],c_carryin),p) cval1b3,q,r=cipher(v1[3],p) cval2b3,q,r=cipher(XOR(v2[3],c_carryin),p) c_sum1,c_carryout=FA(cval1b0,cval2b0,c_carryin ) c_sum2,c_carryout=FA(cval1b1,cval2b1,c_carryout ) c_sum3,c_carryout=FA(cval1b2,cval2b2,c_carryout ) c_sum4,c_carryout=FA(cval1b3,cval2b3,c_carryout ) #decrypt sum1 = (c_sum1 % p) % 2 sum2 = (c_sum2 % p) % 2 sum3 = (c_sum3 % p) % 2 sum4 = (c_sum4 % p) % 2 carryout = (c_carryout % p) % 2 print("Val1:",val1) print("Val2:",val2) print("M:",cin) if (cin==0): print("Val1+Val2") else: print("Val1-Val2") print(v1) print(v2) print("\n-----Results") print("Result:\t\t",sum4,sum3,sum2,sum1) print("Carry-out:\t",carryout) print("\n-----Debug") print("CipherSum1:\t",c_sum1) print("CipherSum2:\t",c_sum2) print("CipherSum3:\t",c_sum3) print("CipherSum4:\t",c_sum4)
A sample run for 10+3 is:
Val1: 10 Val2: 3 M: 0 Val1+Val2 (Adding) [0, 1, 0, 1, 0, 0, 0, 0] [1, 1, 0, 0, 0, 0, 0, 0] -----Results Result: 1 1 0 1 Carry-out: 0 -----Debug CipherSum1: 4780788020972615184037636356588970357364892003040089261340491409257506719577893923768430 CipherSum2: 89671423684912201360104343511602937264468962892714076665973409088687347522314712339767282027318584679975402480980285588390057214001698850054457255 CipherSum3: 2358017890646655622675644104133168115643346532120150675928854421893495855209071244018200443900716576399020311623005978379045240177972244764508753719336028726952200534832698903934657608807751030682064441432 CipherSum4: 54876342233072471157308144932969111822469469025416053168529089023959988881646286901034381555597200698872472618122272211529746139563033760628643347726276938367261416548886632657354373825898213140049400800069585310999764714859249759231134629137560932790605344907543
A sample run for 10-3 is:
Val1: 10 Val2: 3 M: 1 Val1-Val2 (Subtracting) [0, 1, 0, 1, 0, 0, 0, 0] [1, 1, 0, 0, 0, 0, 0, 0] -----Results Result: 0 1 1 1 Carry-out: 1 -----Debug CipherSum1: 2124050351462690486956872522365497181483404383189675872190873442219043664158201562811192 CipherSum2: 32383161150660767767882651893682250629826575985285594303548505757443348232137078711635500951106637365003955782208291404491999823107568768323498947 CipherSum3: 539990443680089821571575952248822269181529058198095204301371515141549295572357440820308632052179835628103635785599570452125830995473506202957097572740284647129586865771558155622358657765587038284281428282 CipherSum4: 7524378550154366937984119476879073248554884906135107094964138842530576582926492026107138548298871336404324183076271851543366006103865632266218577966687006328202649390880359724878228827658265262409843537999865144414851138297830650197352711438247726864105070988058
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.