BGV was proposed by Zvika Brakerski, Craig Gentry and Vinod Vaikuntanathan and is a fully homomorphic encryption method. We encrypt a single bit at a time, and then fit into a circuit. It uses a Ring LWE (Learning With Errors) method [theory].
BGV Homomorphic Cipher |
Code
The following is an outline (and based on [code]):
import math import random import numpy as np bit=0 def setup(l, m, b): q = random.getrandbits(m) q = 10 d = 10 n = 10 chi = 1 N = int(math.ceil((2 * n + 1) * math.log(q, 2))) return (q, d, n, N, chi) def secret_key_gen(params): (q, d, n, N, chi) = params s = np.random.randint(0, q, n + 1) s[0] = 1 return s def public_key_gen(params, sk): (q, d, n, N, chi) = params A = np.random.randint(0, q, N * n) A.resize(N, n) e = np.random.randint(0, q, N) b = np.dot(A, sk[1:]) + 2 * e b.resize(N, 1) A = np.hstack((b, -1 * A)) % q assert all(np.dot(A, sk) % q == (2 * e) % q) return A def enc(params, pk, m): assert m == 0 or m == 1 (q, d, n, N, chi) = params m = np.array([m] + [0] * n) r = np.random.randint(0, 2, N) c = m + np.dot(pk.T, r) return c % q def dec(params, sk, c): (q, d, n, N, chi) = params return (sum(c * sk) % q) % 2 params = setup(1, 1, 1) sk = secret_key_gen(params) pk = public_key_gen(params, sk) c0 = enc(params, pk, bit) print "Message bit:\t",bit print "Public key [0]:\t",pk[0] print "Public key [1]:\t",pk[1] print "Secret key:\t",sk print "Cipher for bit:\t",c0 print "Decrypted bit:\t", dec(params, sk, c0)
Reference
[1] Zvika Brakerski, Craig Gentry and Vinod Vaikuntanathan, Fully Homomorphic Encryption without Bootstrapping, in Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, 2012. [paper]