Python + numpy implementation of homomorphic encryption algorithms

Before realizing this, it's important to understand whathomomorphic encryption。

The following formula makes what we are trying to achievehomomorphic encryptionreleases
$\mathbf{c}=w \mathbf{x}+\mathbf{e} \quad \mathbf{x}=\left\lceil\frac{S \mathbf{c}}{w}\right\rfloor$

The first type of encryption

symmetric encryption

If the key S is a unitary matrix, then c is nothing more than a reweighted, slightly noisy version of the input x.

When S is a unit matrix, it is equivalent to no encryption

When S is a random matrix, there are encrypted

Use the same key for encryption and decryption

import numpy as np

def generate_key(w,m,n):
    S = (np.random.rand(m,n) * w / (2 ** 16))# It can be shown that max(S) < w
    return S# key, symmetric encryption
def encrypt(x,S,m,n,w):
    assert len(x) == len(S)
    e = (np.random.rand(m))# It can be shown that max(e) < w / 2
    c = np.linalg.inv(S).dot((w * x) + e)   
    return c
def decrypt(c,S,w):
    return (S.dot(c) / w).astype('int')

x = np.array([0,1,2,5])
m = len(x)
n = m
w = 16
S = generate_key(w,m,n)

(of a computer) run

c = encrypt(x,S,m,n,w)
decrypt(c,S,w)

array([0, 1, 2, 5])

print(x+x)
print(x*10)

[ 0 2 4 10]
[ 0 10 20 50]

decrypt(c+c,S,w)

array([ 0, 2, 4, 10])

decrypt(c*10,S,w)

array([ 0, 10, 20, 50])

x*x

array([0, 1, 4])

decrypt(c*c,S,w)

array([15296055, 6267577, 8584289])

Second encryption

Instead of explicitly assigning a separate pair of "public key" and "private key", the authors of the paper propose a "key exchange" technique, where the private key S is replaced by S '. More specifically, this private key exchange technique involves generating a matrix that can perform this transformation, M. Since M has the ability to transform a message from an unencrypted state (a unit matrix key) to an encrypted state (a random and hard-to-guess key), this M matrix can be used as our public key!

Based on the opening two equations, if the key is a unitary matrix, then the message is unencrypted.

Based on the opening two equations, the message is encrypted if the key is a random matrix.

We construct a matrix M to convert one key to another private key.

When the matrix M converts the unit matrix into a random key, by definition it encrypts the message using one-way encryption.

Since M acts as a "one-way encryption", we call it a "public key" and can distribute it like a public key because it cannot be used for decryption.

import numpy as np

def generate_key(w,m,n):
    S = (np.random.rand(m,n) * w / (2 ** 16)) # It can be shown that max(S) < w
    return S

def encrypt(x,S,m,n,w):
    assert len(x) == len(S)
    e = (np.random.rand(m)) # It can be shown that max(e) < w / 2
    c = np.linalg.inv(S).dot((w * x) + e)
    return c

def decrypt(c,S,w):
    return (S.dot(c) / w).astype('int')

def get_c_star(c,m,l):
    c_star = np.zeros(l * m,dtype='int')
    for i in range(m):
        b = np.array(list(np.binary_repr(np.abs(c[i]))),dtype='int')
        if(c[i] < 0):
            b *= -1
        c_star[(i * l) + (l-len(b)): (i+1) * l] += b
    return c_star

def switch_key(c,S,m,n,T):
    l = int(np.ceil(np.log2(np.max(np.abs(c)))))
    c_star = get_c_star(c,m,l)
    S_star = get_S_star(S,m,n,l)
    n_prime = n + 1
    S_prime = np.concatenate((np.eye(m),T.T),0).T
    A = (np.random.rand(n_prime - m, n*l) * 10).astype('int')
    E = (1 * np.random.rand(S_star.shape[0],S_star.shape[1])).astype('int')
    M = np.concatenate(((S_star - T.dot(A) + E),A),0)
    c_prime = M.dot(c_star)
    return c_prime,S_prime

def get_S_star(S,m,n,l):
    S_star = list()
    for i in range(l):
        S_star.append(S*2**(l-i-1))
    S_star = np.array(S_star).transpose(1,2,0).reshape(m,n*l)
    return S_star

def get_T(n):
    n_prime = n + 1
    T = (10 * np.random.rand(n,n_prime - n)).astype('int')
    return T

def encrypt_via_switch(x,w,m,n,T):
    c,S = switch_key(x*w,np.eye(m),m,n,T)
    return c,S

(of a computer) run

x = np.array([0,1,3,5])
m = len(x)
n = m
w = 16
S = generate_key(w,m,n)

y = np.array([3,3,3,3])
m = len(y)
n = m
w = 16
S = generate_key(w,m,n)

print(x * 10)
print(x + y)

[ 0 10 30 50]
[3 4 6 8]

T = get_T(n)
cx,S = encrypt_via_switch(x,w,m,n,T)
print(cx)
#T = get_T(n)
cy,S = encrypt_via_switch(y,w,m,n,T)
print(cy)

[-115. -122. -21. -35. 23.]
[-177. -222. -87. -177. 45.]

print(decrypt(cx,S,w))
print(decrypt(cy,S,w))

[0 1 3 5]
[3 3 3 3]

decrypt(cx * 10,S,w)

array([ 0, 10, 30, 50])

decrypt(cx + cy,S,w)

array([3, 4, 6, 8])