This blog post aims at explaining the basic mathematical concepts behind most of today's homomorphic encryption (HE) schemes, and then build upon this to implement our own scheme (similar to BFV) from scratch using Python. This post assumes general knowledge of HE and its terminology, if you have no idea what HE is, then you should check my previous blog post for a quick introduction.

We will start by introducing the hard problem behind most of today's HE schemes, namely, learning with error and its variant ring learning with error, if you are familiar with these concepts then you may want to jump directly to the implementation section, but just before, we need to agree on some basic notation.

Basic Notation

We denote by the set of integers where is an integer, all integer operations will be performed if not stated otherwise, and for simplicity, you will see me mostly deal with positive integers in , but keep in mind that it's the same as our , as where is a positive integer (e.g. ). An element would be simply a vector of elements in . We will use to specify that we are applying modulo , and for rounding to the nearest integer.

We denote by the inner product of two elements and is defined as follows:

Learning With Error & Ring Learning With Error

Learning With Error (LWE) was introduced by Regev in 2009 and can be defined as follows: For integers and , let's consider the following equations

where and are chosen independently and uniformly from , and are chosen independently according to a probability distribution over , and . The LWE problem state that it's hard to recover from the pairs , and it's on such hardness that cryptography generally lies. On the list of candidate algorithms for the post-quantum cryptography standardization are some that are based on LWE, so you would probably hear more about it when it would be used in key-establishement and public-key encryption.

Ring-LWE is a variant of LWE, it's still based on the hardness of recovering from the pairs , and the equations are mainly the same, however, we go from the world of integers () to the world of polynomial quotient rings (), this means that we will deal with polynomials with coefficients in , and the polynomial operations are done some polynomial that we call the polynomial modulus (in our case: ), so all polynomials should be of degree , and .

Let's now use a more formal definition of RLWE by Regev: Let be a power of two, and let be a prime modulus satisfying . Define as the ring containing all polynomials over the field in which is identified with . In ring-LWE we are given samples of the form where is a fixed secret, is chosen uniformly, and is an error term chosen independently from some error distribution over .

So if we want to build an HE scheme using RLWE, then our basic elements won't be integers, but polynomials, and you should be familiar with basic polynomial operations (addition, multiplication and modulo). I cooked up a quick refresher of polynomial operations to avoid getting off on the wrong foot, but you can just skip it if it's a trivial thing for you.

Note: All the polynomials in the below examples (addition and multiplication) are in

Addition

Let's add two polynomials and

The below modulo operation is useless but I just wanted to show that all operations are performed modulo our polynomial modulus.

Multiplication

Now we multiply two simpler polynomials and

is the remainder of the division of by as you may see below:

Don't panic! We will write these operations in Python in the next section so you won't have to do these calculations anymore.

Build an Homomorphic Encryption Scheme

Disclaimer: This implementation doesn't neither claim to be secure nor does it follow software engineering best practices, it is designed as simple as possible for the reader to understand the concepts behind homomorphic encryption schemes.

In this section, we go through an implementation of an homomorphic encryption scheme which is mainly inspired from BFV. We have split the whole scheme into basic functionalities, key-generation, encryption, decryption and evaluation (add and mul). Each functionality would be first explained then implemented in Python. The full implementation can be found on this github gist.

We start by importing the amazing Numpy library, then we define two helper functions (polyadd and polymul) for adding and multiplying polynomials over a ring .

import numpy as np
from numpy.polynomial import polynomial as poly

def polymul(x, y, modulus, poly_mod):
    """Add two polynoms
    Args:
        x, y: two polynoms to be added.
        modulus: coefficient modulus.
        poly_mod: polynomial modulus.
    Returns:
        A polynomial in Z_modulus[X]/(poly_mod).
    """
    return np.int64(
        np.round(poly.polydiv(poly.polymul(x, y) % modulus, poly_mod)[1] % modulus)
    )


def polyadd(x, y, modulus, poly_mod):
    """Multiply two polynoms
    Args:
        x, y: two polynoms to be multiplied.
        modulus: coefficient modulus.
        poly_mod: polynomial modulus.
    Returns:
        A polynomial in Z_modulus[X]/(poly_mod).
    """
    return np.int64(
        np.round(poly.polydiv(poly.polyadd(x, y) % modulus, poly_mod)[1] % modulus)
    )

Key Generation

We start by generating a random secret-key from a probability distribution, we will use the uniform distribution over , which means will be a polynomial with coefficients being or . For the public-key we first sample a polynomial uniformly over and a small error polynomial from a discrete normal distribution over . We then set the public-key to be the tuple . So let's first implement the generation of polynomials from different probability distributions.

def gen_binary_poly(size):
    """Generates a polynomial with coeffecients in [0, 1]
    Args:
        size: number of coeffcients, size-1 being the degree of the
            polynomial.
    Returns:
        array of coefficients with the coeff[i] being 
        the coeff of x ^ i.
    """
    return np.random.randint(0, 2, size, dtype=np.int64)


def gen_uniform_poly(size, modulus):
    """Generates a polynomial with coeffecients being integers in Z_modulus
    Args:
        size: number of coeffcients, size-1 being the degree of the
            polynomial.
    Returns:
        array of coefficients with the coeff[i] being 
        the coeff of x ^ i.
    """
    return np.random.randint(0, modulus, size, dtype=np.int64)


def gen_normal_poly(size):
    """Generates a polynomial with coeffecients in a normal distribution
    of mean 0 and a standard deviation of 2, then discretize it.
    Args:
        size: number of coeffcients, size-1 being the degree of the
            polynomial.
    Returns:
        array of coefficients with the coeff[i] being 
        the coeff of x ^ i.
    """
    return np.int64(np.random.normal(0, 2, size=size))

Then we can define our key-generator using these functions

def keygen(size, modulus, poly_mod):
    """Generate a public and secret keys
    Args:
        size: size of the polynoms for the public and secret keys.
        modulus: coefficient modulus.
        poly_mod: polynomial modulus.
    Returns:
        Public and secret key.
    """
    sk = gen_binary_poly(size)
    a = gen_uniform_poly(size, modulus)
    e = gen_normal_poly(size)
    b = polyadd(polymul(-a, sk, modulus, poly_mod), -e, modulus, poly_mod)
    return (b, a), sk

The public-key (b, a) can then be used for encryption, and the secret-key sk for decryption.

Encryption

Our scheme will support encryption of polynomials in the ring where is called the plaintext modulus. In our case we will want to encrypt integers in so we will need to encode this integer into the plaintext domain , we will simply encode an integer (for plaintext) as the constant polynomial (e.g. will hold the value of 5 ). The encryption algorithm takes a public-key and a plaintext polynomial and outputs a ciphertext , which is a tuple of two polynomials and and they are computed as follows: