Building A Fully Homomorphic Encryption Scheme in Python

Building A Fully Homomorphic Encryption Scheme in Python

by

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)

Basic Notation

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 n≥1 and q≥2 integers.

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  Rq=Zq/⟨xn+1⟩.

The Algorithm

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.

Security

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

Let ct be a ciphertext encrypting message m1 in plaintext; it is important to recall the structure of our ciphertext.

adding a plaintext message m2 results:

We will just need to scale our new plaintext m2 by δ and add it to ct0.

The decryption looks like this after the addition:

Let ct be a ciphertext encrypting a plaintext message m1, and we want to multiply it with a plaintext message m2, which will result to:

Multiplying ct0 with 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:

Key Generation

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 pk=([−(a⋅sk+e)]q,a).

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
    Args:
        sk: secret-key.
        size: size of polynomials.
        q: ciphertext modulus.
        t: plaintext modulus.
        poly_mod: polynomial modulus.
        ct: ciphertext.
    Returns:
        Integer representing the plaintext.
    """
    scaled_pt = polyadd(
            polymul(ct[1], sk, q, poly_mod),
            ct[0], q, poly_mod
        )
    decrypted_poly = np.round(scaled_pt * t / q) % t
    return int(decrypted_poly[0])

Evaluation

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.

Conclusion

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! 

Leave a Comment