This page uses the method on homomorphic encryption from DGHV (Dijk, Gentry, Halevi and Vaikuntanathan). It converts two integers to bits and then EX-ORs each of them using cipher versions of the bits:
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:
# https://asecuritysite.com/encryption/hom_xor 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 range(len(bits1))] c_bits2 = [0 for i in range(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.