This article aims to discuss building a fully homomorphic encryption scheme in python.
What is Homomorphic Encryption?
Homomorphic encryption is a type of encryption that lets users do the math on encrypted data without first having to decrypt it.
The word Homomorphic comes from the word Homomorphism, which is used in algebra.
With this type of encryption, data can be encrypted and sent to cloud services or environments to be processed without being able to access the raw data.
Also read: Python head Function with Example Program
Types of Homomorphic Encryption
- Partially Homomorphic Encryption (PHE)
- Somewhat Homomorphic Encryption (SHE)
- Fully Homomorphic Encryption (FHE)
Zq represents the set of integers (−q/2,q/2] where q>1 is an integer, all integer operations will be performed mod q. For convenience, I will largely deal with positive integers in [0,q), but keep in mind that it’s the same as our Zq, as −x≡q−x(mod q) where x is a positive integer (e.g. −1≡6(mod 7)).
An element v ∈ Znq would be a vector containing n elements from Zq. We shall use [⋅]m to indicate an application modulo m, and ⌊⋅⌉ to round to the nearest integer. ⟨a,b⟩ represents the inner product of two components a,b∈Znq and is defined as follows:
Learning with Errors
In 2009, Regev invented Learning With Error (LWE), which can be described as follows: Consider the following equations involving
It means that we might homomorphically evaluate a circuit of polynomial utilizing the above approach from ring LWE.
Build a Homomorphic Encryption Scheme in Python
This section describes an implementation of a homomorphic encryption system that is mostly influenced by BFV. We have subdivided the entire technique into key generation, encryption, decryption, and evaluation.
Then we construct two helper functions addition and multiplication of polynomials over the ring
The key generation algorithm produces two keys: a public key that can encrypt messages and a secret key that can decrypt messages. We are aware that the encryption conceals our message by encasing it in two layers: a layer of minor mistake terms in green and a layer that can only be removed with the secret key.
As we will see in the following section, computing these encrypted numbers will increase the green layer, and if we are not careful, it may explode and obscure our encrypted value, rendering it impossible to decipher correctly.
If you are concerned about the security of HE schemes and how easily they can be cracked in the near future, you should know that the majority of existing schemes use post-quantum secure lattice-based encryption.
Remember that there is no algorithm that can break the security of these types of schemes in polynomial time on either classical or quantum computers; the best-known attack runs in exponential time.
Addition and Multiplication
ct be a ciphertext encrypting message
m1 in plaintext; it is important to recall the structure of our ciphertext.
adding a plaintext message
We will just need to scale our new plaintext
δ and add it to
The decryption looks like this after the addition:
ct be a ciphertext encrypting a plaintext message
m1, and we want to multiply it with a plaintext message
m2, which will result to:
m2 will result in:
expanding the public-key terms in
[ct0+ct1⋅sk]q reveals that it won’t decrypt correctly.
For correct decryption, we will also need to multiply
ct1 by m2
Then we end up with:
We begin by generating a random secret key
sk from a probability distribution. We will use the uniform distribution over
R2 , therefore
sk will have coefficients of 0 or 1.
We then sample a polynomial a uniformly over
Rq and a tiny error polynomial e from a discrete normal distribution over
Rq for the public key. The public key is then set to the tuple
Encryption and Decryption
The scheme will be capable of encrypting polynomials in the ring Rt=Zt/xn+1 , where t is the plaintext modulus. In our scenario, we will want to encrypt integers in Zt , thus we will encode this integer into the plaintext domain Rt.
To do so, we will encode an integer pt as the constant polynomial m(x)=pt (e.g., m(x)=5 will hold the value 5). The encryption technique generates a public-key polynomial pk∈Rq×Rq and a plaintext polynomial m∈Rt as inputs and generates ciphertext ct∈RqxRq, which is a pair of two polynomials ct0 and ct1 computed as follows:
The first intuition behind decryption is that (pk1⋅sk≈−pk0) which means that they sum up to a really small polynomial.
def decrypt(sk, size, q, t, poly_mod, ct):
"""Decrypt a ciphertext
size: size of polynomials.
q: ciphertext modulus.
t: plaintext modulus.
poly_mod: polynomial modulus.
Integer representing the plaintext.
scaled_pt = polyadd(
polymul(ct, sk, q, poly_mod),
ct, q, poly_mod
decrypted_poly = np.round(scaled_pt * t / q) % t
Now that we know how to generate keys, encrypt, and decrypt, we learn how to compute encrypted data. Having a ciphertext in hand, we can add or multiply it with other ciphertexts or plaintexts.
You should be pleased with yourself for understanding the mathematics of building a fully homomorphic encryption scheme in python.
I sincerely hope it was successful!