Data Processing Becomes Anonymised

Data Processing Becomes Anonymised

We need to move to an information world where every single data element is be encrypted at every point, no matter if it is at rest, in motion, or in process. The in-process part is our greatest challenge, and only homomorphic encryption will solve this problem. In the future our data processors may operate on encrypted values.

One of the best methods around for full homomorphic encryption is BGV. It was proposed by Zvika Brakerski, Craig Gentry and Vinod Vaikuntanathan [paper].

With BGV, we encrypt a single bit at a time, and then fit into a circuit. Overall it uses a Ring LWE (Learning With Errors) method [theory]. 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)

A sample run is:

====Parameters=====
q= 10
n= 10
N= 70

====Keys==========
Public key [0]: [8 6 1 5 6 0 8 7 3 5 6]
Public key [1]: [8 2 7 6 3 0 2 6 6 7 6]
…
Public key [N-1]: [0 4 7 6 5 2 3 8 7 4 6]
Secret key: [1 6 9 1 2 1 6 8 5 7 1]

====Ciphers=======
Message bit: 1
Cipher for bit: [0 7 3 8 2 5 4 8 4 0 1]
Decrypted bit: 1

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, https://eprint.iacr.org/2011/277.pdf