With the DGHV (Dijk, Gentry, Halevi and Vaikuntanathan) method we can implement a fully homomorphic encryption scheme [1]. We can use symmetric key encryption by sharing the secret value (p), but we can turn it into a public key method by ciphering a number of zero-value cipher bits:
Simple Homomorphic Cipher with Public Key Encryption |
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).
With public key we create many values of message bits of value of zero ("encryptions of zero").
In order to convert to a public key method we create a number of integers with the message bits of zero (m=0). We can then publish these public key values. For \(x_i\) values we create random q and r values:
\(x_i = p \times q_i + 2 \times r_i \)
For example for 32 public key values we can implement as:
print "Public key: ", for i in range(0,len(public_key)): r =randint(1, 10) q =randint(50000, 60000) public_key[i] = q * p + 2*r print public_key[i], print
To encrypt a bit (m) we take the m bit and add it to a sum of a subset of \(x_i\).
Code
The following is an outline:
# https://asecuritysite.com/encryption/hom_public import sys from random import randint 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=8 if (len(sys.argv)>1): val1=int(sys.argv[1]) p =randint(1000000, 2000000)*2+1 bits = to_bin(val1) public_key = [0 for i in range(32)] cipher = [0 for i in range(len(bits))] print("Value:\t",val1," Input data:",bits) print("\np value:\t",p) print() print("Public key: ", end=' ') for i in range(0,len(public_key)): r =randint(1, 10) q =randint(50000, 60000) public_key[i] = q * p + 2*r print(public_key[i], end=' ') print() print("\nCipher bits:\t", end=' ') for i in range(0,len(bits)): j1 = randint(0,len(public_key)-1) j2 = randint(0,len(public_key)-1) j3 = randint(0,len(public_key)-1) sum = public_key[j1]+public_key[j2]+public_key[j3] r =randint(1, 10) cipher[i]=sum+2*r+bits[i] print(cipher[i], end=' ') print() print("\nDecipher bits:\t", end=' ') for i in range(0,len(bits)): print((cipher[i] % p) %2, end=' ')
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.