Fully Homomorphic Encryption from Scratch

03 Jan 2024

Introduction

Fully Homomorphic Encryption (FHE) is a form of encryption that makes it possible to evaluate functions on encrypted inputs without access to the decryption key. For example, suppose you want to use a neural network running on an untrusted server to determine whether your image contains a cat. Since the server is untrusted, you do not want it to see your image. With FHE you can encrypt the image with your secret key and upload the encrypted image to the server. The server can then apply its neural network to the encrypted image and produce an encrypted bit. You can then download the encrypted bit and decrypt it with your secret key to obtain the result.

In other words, FHE makes it possible to leverage the computational resources of an untrusted server without having to send it any unencrypted data.

At first glance it seems like FHE is impossible. Encrypted data should be indistinguishable from random bytes to a person without access to the encryption key. So how could such a person perform a meaningful calculation on the encrypted data?

In this post we will explore a popular FHE encryption scheme called TFHE and implement it from scratch in Python. All of the code in this post together with tests can be found here: https://github.com/lowdanie/tfhe

The standard cryptography exposition disclaimer applies. Namely, that it probably is not a good idea to copy paste code from this post to secure your sensitive data. You can use the official TFHE library instead.

A Fully Homomorphic NAND Gate

Any boolean function can be implemented with a combination of NAND gates. Therefore, in this post we’ll focus on implementing a homomorphic version of the NAND gate which can be evaluated on encrypted inputs.

Specifically, we’ll implement generate_key, encrypt and decrypt functions:

def generate_key() -> EncryptionKey:
    pass

def encrypt(plaintext: Plaintext, key: EncryptionKey) -> Ciphertext:
    pass

def decrypt(ciphertext: Ciphertext, key: EncryptionKey) -> Plaintext:
    pass

and a homomorphic NAND gate:

def homomorphic_nand(
    ciphertext_left: Ciphertext,
    ciphertext_right: Ciphertext,
) -> Ciphertext:
    """Homomorphically evaluate the NAND function."""
    pass

The homomorphic property will allow us to perform the following type of computation:

# Client side: Create an encryption key and encrypt two bits.
client_key = generate_key()

b_0 = True
b_1 = False

ciphertext_0 = encrypt(b_0, client_key)
ciphertext_1 = encrypt(b_1, client_key)

# The client sends the ciphertexts to the server.

# Server side: Compute an encryption of NAND(b_0, b_1) from
# the two ciphertexts:
ciphertext_nand = homomorphic_nand(ciphertext_0, ciphertext_1)

# The server sends ciphertext_nand back to the client.

# Client side: Decrypt ciphertext_nand.
# The result should be equal to NAND(True, False) = True
result = decrypt(ciphertext_nand, client_key)
assert result

Importantly, the server never receives the client_key and so it is not able to read the contents of ciphertext_left or ciphertext_right. Nevertheless, it can run the homomorphic_nand function on the ciphertexts to produce ciphertext_nand which encrypts NAND(b_0, b_1). Without the client_key, the server cannot read the contents of ciphertext_nand. All it can do is send ciphertext_nand back to the client who can use their client_key to decrypt it and reveal the result.

Of course, all of this complexity is unnecessary if the client is only interested in evaluating a single NAND gate. The client would be better off just evaluating the NAND function locally not involving a server at all.

Homomorphic encryption becomes more useful when the client wants to evaluate a complex circuit such as a neural network which is composed of many billions of NAND gates. In that case the client may not have the compute or the permission to run the program locally. Instead they can offload the computation to an untrusted server using the approach in the code snippet above, where the homomorphic_nand function is used by the server to evaluate each of the NAND gates in the complex circuit.

The goal of this post is to implement generate_key, encrypt, decrypt and homomorphic_nand.

Learning With Errors

In this section we wil implement generate_key, encrypt and decrypt. This combination of functions is typically called an Encryption Scheme.

Encryption schemes are usually based on a fundamental mathematical problem that is assumed to be “hard”. For example, RSA is based on the assumption that is is hard to find the prime factors of large integers. Similarly, TFHE is based on a problem called Learning With Errors (LWE). In the next section we will define the LWE problem and use it to construct an encryption scheme.

As we will see, in the LWE encryption scheme it is possible to homomorphically add ciphertexts but not to homomorphically multiply them. This type of encryption scheme is called Partially Homomorphic because not all operations are supported. Despite this limitation, the partially homomorphic operations in the LWE scheme will be useful stepping stones on the path towards fully homomorphic encryption.

In this section we will define the Learning With Errors (LWE) problem and use it to implement our encryption scheme as well as some homomorphic operations.

Notation

Let $q$ be a positive integer. We will denote the integers modulo $q$ by ${\mathbb{Z}}_q:=\mathbb{Z}/q\mathbb{Z}$. In this post, it will be convenient to set $q=2^{32}$ so that elements of ${\mathbb{Z}}_q$ can be represented by the signed 32-bit integers: $[-2^{31},2^{31})$. One advantage of using 32-bit integers is that all operations are natively done modulo $2^{32}$.

Similarly, ${\mathbb{Z}}_8$ will denote the integers modulo $8$. We will identify ${\mathbb{Z}}_8$ with the set of integers $[-4,4)$.

The Learning With Errors Problem

Let $\mathbf{s}\in {\mathbb{Z}}_q^n$ be a length $n$ vector with elements in ${\mathbb{Z}}_q$ which is assumed to be secret. Let ${\mathbf{a}}_1,\dots ,{\mathbf{a}}_m\in {\mathbb{Z}}_q^n$ be random vectors and let $b_i={\mathbf{a}}_i\cdot \mathbf{s}$ be the dot product of ${\mathbf{a}}_i$ with $\mathbf{s}$. As a warmup to the LWE problem we can ask:

Given $m\ge n$ random vectors ${\mathbf{a}}_1,\dots ,{\mathbf{a}}_m$ and the dot products $b_i,\dots ,b_m$, is it possible to efficiently learn the secret vector $\mathbf{s}$?

It is not hard to see that the answer is “yes”. Indeed, we can create an $m\times n$ matrix $A$ whose rows are the vectors ${\mathbf{a}}_i$ and a length $m$ vector $\mathbf{b}$ whose elements are $b_i$:

$$A={\left[\begin{array}{c}{\mathbf{a}}_1^T\\ ⋮\\ {\mathbf{a}}_m^T\end{array}\right]}_{m\times n}\mathbf{b}=\left[\begin{array}{c}{b}_1\\ ⋮\\ b_m\end{array}\right]$$

We can then express $\mathbf{s}$ as the solution to the linear equation:

$$A\mathbf{s}=\mathbf{b}$$

Finally, we can use Gaussian Elimination to solve for $\mathbf{s}$ in polynomial time. Note that the standard Gaussian elimination algorithm has to be tweaked a bit to account for the fact that ${\mathbb{Z}}_q$ is not a field - but the general idea is the same.

We can think of the above problem as Learning Without Errors since we are given the exact dot products $b_i={\mathbf{a}}_i\cdot \mathbf{s}$. It turns out that if we introduce errors by adding a bit of noise $e_i$ to each $b_i$, then learning $\mathbf{s}$ from the random vectors ${\mathbf{a}}_i$ and the noisy dot products $b_i={\mathbf{a}}_i\cdot \mathbf{s}+e_i$ is very hard. We can now state the Learning With Errors problem:

Given $m$ random vectors ${\mathbf{a}}_1,\dots ,{\mathbf{a}}_m$ and noisy dot products $b_i={\mathbf{a}}_i\cdot \mathbf{s}+e_i$, is it possible to efficiently learn the secret vector $\mathbf{s}$?

Note that we have not yet specified which distribution the errors $e_i\in {\mathbb{Z}}_q$ are drawn from. In TFHE, they are sampled by first sampling a real number $-\frac{1}{2}\le x_i<\frac{1}{2}$ from a Gaussian distribution $\mathcal{N}(0,\sigma )$ with $\sigma \ll 1$, and then scaling $x$ by $q$ to obtain a number in the interval $[-\frac{q}{2},\frac{q}{2})$ and finally rounding to the nearest integer:

We will denote the distribution on ${\mathbb{Z}}_q$ obtained in this way by ${\mathcal{N}}_q(0,\sigma )$.

In the next section we will see how to build a partially homomorphic encryption scheme based on the hardness of LWE.

An LWE Based Encryption Scheme

Following the notation of the previous section, our encryption scheme will be parameterized by a modulus $q$, a dimension $n$ and a noise level $\sigma$. Typical values would be $q=2^{32}$, $n=500$ and $\sigma =2^{-20}$.

The valid inputs to an encryption function are known as the message space. The message space of the LWE scheme is ${\mathbb{Z}}_q$. We will also call valid messages plaintexts.

The encryption keys are random length $n$ binary vectors $\mathbf{s}\in \{0,1{\}}^n\subset {\mathbb{Z}}_q^n$.

To encrypt a message $m\in {\mathbb{Z}}_q$ with a key $\mathbf{s}\in {\mathbb{Z}}_q^n$ we first uniformly sample a vector $\mathbf{a}\in {\mathbb{Z}}_q^n$ and sample a noise element $e\in {\mathbb{Z}}_q$ from the Gaussian distribution ${\mathcal{N}}_q(0,\sigma )$. The encrypted message, also known as the ciphertext, is defined to be the pair

$${\mathrm{Enc}}_{\mathbf{s}}(m):=(\mathbf{a},\mathbf{a}\cdot \mathbf{s}+m+e)\in {\mathbb{Z}}_q^n\times {\mathbb{Z}}_q$$

If we know the secret key $\mathbf{s}$, we can decrypt a ciphertext $(\mathbf{a},b)$ by computing:

$${\mathrm{Dec}}_{\mathbf{s}}((\mathbf{a},b))=b-\mathbf{a}\cdot \mathbf{s}=(\mathbf{a}\cdot \mathbf{s}+m+e)-\mathbf{a}\cdot \mathbf{s}=m+e$$

In section Message Encoding we’ll describe a method for removing the error term $e$ in the equation above so that we can recover the exact message $m$ after decryption.

Note that the encryption function is not deterministic since it samples from the distribution ${\mathcal{N}}_q(0,\sigma )$. It turns out that this is a feature and not a bug. Indeed, any semantically secure encryption scheme must have a non-deterministic encryption function. To see why, suppose we use the scheme to encrypt yes/no responses to a poll. If the encryption function was deterministic, we could tell if two people voted the same way by comparing their encrypted responses. In a non-deterministic scheme, this attack no longer works since even two people that voted the same way will have different encrypted responses.

Let $m$ be an LWE plaintext. Since the encryption function is non-deterministic, rather than saying that a ciphertext $L=(\mathbf{a},b)$ is the encryption of $m$ we will say that it is an encryption of $m$. The set of valid encryptions of $m$ with key $\mathbf{s}$ will be denoted ${\mathrm{LWE}}_{\mathbf{s}}(m)$. If $L={\mathrm{Enc}}_{\mathbf{s}}(m)$ then $L$ is an encryption of $m$ and so we can write:

$$L\in {\mathrm{LWE}}_{\mathbf{s}}(m)$$

Here is an implementation of the LWE encryption scheme:

import dataclasses

import numpy as np

from tfhe import utils
@dataclasses.dataclass
class LweConfig:
    # Size of the LWE encryption key.
    dimension: int

    # Standard deviation of the encryption noise.
    noise_std: float


@dataclasses.dataclass
class LwePlaintext:
    message: np.int32


@dataclasses.dataclass
class LweCiphertext:
    config: LweConfig
    a: np.ndarray  # An int32 array of size config.dimension
    b: np.int32


@dataclasses.dataclass
class LweEncryptionKey:
    config: LweConfig
    key: np.ndarray  # An int32 array of size config.dimension


def generate_lwe_key(config: LweConfig) -> LweEncryptionKey:
    return LweEncryptionKey(
        config=config,
        key=np.random.randint(
            low=0, high=2, size=(config.dimension,), dtype=np.int32
        ),
    )


def lwe_encrypt(
    plaintext: LwePlaintext, key: LweEncryptionKey
) -> LweCiphertext:
    a = utils.uniform_sample_int32(size=key.config.dimension)
    noise = utils.gaussian_sample_int32(std=key.config.noise_std, size=None)

    # b = (a, key) + message + noise
    b = np.add(np.dot(a, key.key), plaintext.message, dtype=np.int32)
    b = np.add(b, noise, dtype=np.int32)

    return LweCiphertext(config=key.config, a=a, b=b)


def lwe_decrypt(
    ciphertext: LweCiphertext, key: LweEncryptionKey
) -> LwePlaintext:
    return LwePlaintext(
        np.subtract(ciphertext.b, np.dot(ciphertext.a, key.key), dtype=np.int32)
    )

where the utils module contains:

from typing import Optional

import numpy as np

INT32_MIN = np.iinfo(np.int32).min
INT32_MAX = np.iinfo(np.int32).max


def uniform_sample_int32(size: int) -> np.ndarray:
    return np.random.randint(
        low=INT32_MIN,
        high=INT32_MAX + 1,
        size=size,
        dtype=np.int32,
    )


def gaussian_sample_int32(std: float, size: Optional[float]) -> np.ndarray:
    return np.int32(INT32_MAX * np.random.normal(loc=0.0, scale=std, size=size))

Throughout this post, we will used the following LweConfig whose parameters are taken from the popular Lattice Estimator.

from tfhe import lwe

LWE_CONFIG = lwe.LweConfig(dimension=1024, noise_std=2 ** (-24))

Ciphertext Noise

Let $m\in {\mathbb{Z}}_q$ be an LWE plaintext and let $\mathbf{s}$ be an LWE encryption key. Let $L\in {\mathrm{LWE}}_{\mathbf{s}}(m)$ be an LWE encryption of $m$. In the previous section we saw that:

$${\mathrm{Dec}}_{\mathbf{s}}(L)=m+e$$

where $e$ is some small noise whose magnitude depends on the LWE parameters. In other words, when we decrypt $L$ we get the original message $m$ together with a small error term. We will call $e$ the noise in the ciphertext $L$.

As an example, we’ll use the code above to encrypt the message $m=2^{29}$ one thousand times and plot a histogram of the ciphertext noise. We’ll use the LWE config above where the encryption noise has a standard deviation of $\sigma =2^{-24}$. Since we multiply this by $q/2=2^{31}$ during encryption following equation $\text{1}$, we expect the ciphertext noise to have a standard deviation of roughly ${\sigma }^{\prime }=2^{31-24}=2^7=128$.

# Generate an LWE key.
key = lwe.generate_lwe_key(config.LWE_CONFIG)

# This is the plaintext that we will encrypt.
plaintext = lwe.LwePlaintext(2**29)

# Encrypt the plaintext 1000 times and store the error of each ciphertext.
errors = []
for _ in range(1000):
    ciphertext = lwe.lwe_encrypt(plaintext, key)
    errors.append(lwe.lwe_decrypt(ciphertext, key).message - plaintext.message)

Here is a histogram of errors:

This matches our estimated standard deviation of ${\sigma }^{\prime }=128$ pretty well.

Message Encoding

In the previous section we saw that when we decrypt a ciphertext with LWE we get the original message plus a small error. For some applications such as neural networks a small amount of error may be tolerable. An alternative approach is to restrict the set of possible messages so that a message $m$ can be recovered from $m+e$ by rounding to the nearest message in the restricted set.

For the purposes of this post we will only need to distinguish between 8 different messages and so all of our messages will be of the form $m=i\cdot 2^{29}$ where $i\in {\mathbb{Z}}_8=[-4,4)$.

Here is a depiction of ${\mathbb{Z}}_q$ as a circle starting from $2^{31}$ in the “3 o’clock” position and going counter clockwise all the way around to $-2^{31}$. Note that $2^{31}=-2^{31}$ modulo $q=2^{32}$ which is why we are depicting ${\mathbb{Z}}_q$ as a closed circle. The eight messages $-4\cdot 2^{29},\dots ,3\cdot 2^{29}$ are drawn as blue dots:

We will use the following encoding function to encode an integer $i\in {\mathbb{Z}}_8$ as an LWE plaintext in ${\mathbb{Z}}_q$ (i.e as a 32-bit integer):

Similarly, we will use the following decoding function to convert a 32-bit LWE plaintext in ${\mathbb{Z}}_q$ back to an integer in ${\mathbb{Z}}_8$:

where $\lfloor \cdot \rceil$ denotes rounding to the nearest integer. In terms of the image above, the decoding function maps a point on the circle to the nearest blue dot.

The thick segment of the circle depicts points whose distance from the message $m=3\cdot 2^{29}$ is less than $2^{28}$. Note that for the points in this segment, the closest blue dot is $m=3\cdot 2^{29}$. In general, if $i\in {\mathbb{Z}}_8$ and $|e|<2^{28}$ then

$$\mathrm{Decode}(\mathrm{Encode}(i)+e)=i$$

In the previous section we saw that, using our standard LWE parameters, the distribution of LWE ciphertext errors has a standard deviation of around $2^7$ which is significantly less than $2^{28}$. This means that if $m=\mathrm{Encode}(i)$ and $L\in {\mathrm{LWE}}_{\mathbf{s}}(m)$ is an encryption of $m$ then we can decrypt $L$ and remove the noise by decoding:

In summary, if we only encrypt messages that are encodings of ${\mathbb{Z}}_8$ then we can use the decoding function to remove the noise from our decryption results.

Here is an implementation of the encoding and decoding functions:

def encode(i: int) -> np.int32:
    """Encode an integer in [-4, 4) as an int32"""
    return np.multiply(i, 1 << 29, dtype=np.int32)


def decode(i: np.int32) -> int:
    """Decode an int32 to an integer in the range [-4, 4) mod 8"""
    d = int(np.rint(i / (1 << 29)))
    return ((d + 4) % 8) - 4

def lwe_encode(i: int) -> LwePlaintext:
    """Encode an integer in [-4,4) as an LWE plaintext."""
    return LwePlaintext(utils.encode(i))


def lwe_decode(plaintext: LwePlaintext) -> int:
    """Decode an LWE plaintext to an integer in [-4,4) mod 8."""
    return utils.decode(plaintext.message)

In the following example we’ll use the encoding and decoding functions to encrypt a message and recover the exact message without noise after decryption.

key = lwe.generate_lwe_key(config.LWE_CONFIG)

# Encode the number 2 as an LWE plaintext
plaintext = lwe.lwe_encode(2)

# Encrypt the plaintext
ciphertext = lwe.lwe_encrypt(plaintext, key)

# Decrypt the ciphertext. The result will contain noise.
decrypted = lwe.lwe_decrypt(ciphertext, key)

# Decode the result of the decryption. The decoded decryption
# should be exactly equal to the initial message of 2.
decoded = lwe.lwe_decode(decrypted)

assert decoded == 2

Homomorphic Operations

In the next two sections we will show that the LWE scheme above is homomorphic under addition and multiplication by a plaintext.

More precisely, we will define a homomorphic addition function $\mathrm{CAdd}$ with the following signature:

$$\mathrm{CAdd}:{\mathrm{LWE}}_{\mathbf{s}}(m_1)\times {\mathrm{LWE}}_{\mathbf{s}}(m_2)\to {\mathrm{LWE}}_{\mathbf{s}}(m_1+m_2)$$

In other words, $\mathrm{CAdd}$ takes as input encryptions of $m_1$ and $m_2$ and outputs an encryption of $m_1+m_2$.

Similarly, let $c\in {\mathbb{Z}}_q$ be an LWE plaintext. We will define a homomorphic “multiplication by $c$” function $\mathrm{PMul}$ with the signature:

$$\mathrm{PMul}(c,\cdot ):{\mathrm{LWE}}_{\mathbf{s}}(m)\to {\mathrm{LWE}}_{\mathbf{s}}(c\cdot m)$$

In other words, $\mathrm{PMul}$ takes as input a plaintext $c$ and an encryption of $m$ and outputs an encryption of $c\cdot m$.

Importantly, these homomorphic operations operate only on ciphertexts and do not receive the secret key $\mathbf{s}$ as an input.

We will add these operations to our library by implementing the following methods:

def lwe_add(
    ciphertext_left: LweCiphertext, ciphertext_right: LweCiphertext
) -> LweCiphertext:
    """Homomorphically add two LWE ciphertexts.

    If ciphertext_left is an encryption of m_left and ciphertext_right is
    an encryption of m_right then the output will be an encryption of
    m_left + m_right.
    """
    pass


def lwe_plaintext_multiply(c: int, ciphertext: LweCiphertext) -> LweCiphertext:
    """Homomorphically multiply an LWE ciphertext with a plaintext integer.

    If the ciphertext is an encryption of m then the output will be an
    encryption of c * m.
    """
    pass

Before showing how this works let’s take a minute to explain why this is both interesting and useful. Suppose a server hosts a simple linear regression model with weights $w_0$ and $w_1$ whose linear part is defined by:

$$f(x_0,x_1)=w_0\cdot x_0+w_1\cdot x_1$$

In addition, suppose you have two secret numbers $m_0$ and $m_1$ and you want to use an untrusted server to compute $f(m_0,m_1)$. Since the server is untrusted, you do not want to send $m_0$ or $m_1$. Instead you can leverage the homomorphic addition and multiplication methods above to run the following computation:

# Client side: Generate and encryption key and encrypt m_0 and m_1
key = lwe.generate_lwe_key(config.LWE_CONFIG)
ciphertext_0 = lwe.lwe_encrypt(m_0, key)
ciphertext_1 = lwe.lwe_encrypt(m_1, key)

# Send the ciphertexts to the untrusted server.

# Server side: Generate an encryption of
# f(m_0, m_1) = w_0*m_0 + w_1*m_1
ciphertext_result = lwe.lwe_add(
    lwe.lwe_plaintext_multiply(w_0, ciphertext_0),
    lwe.lwe_plaintext_multiply(w_1, ciphertext_1),
)

# The server sends ciphertext_f back to the client

# Client side: Decrypt ciphertext_result to obtain f(m_0, m_1)
result = lwe.lwe_decrypt(ciphertext_result, key)

Note that this example can easily be extended to general dot products between a vector of weights $\mathbf{w}$ and a vector of features $\mathbf{x}$ which is a core component of neural networks.

Homomorphic Addition

In this section we’ll implement the homomorphic addition function:

$$\mathrm{CAdd}:{\mathrm{LWE}}_{\mathbf{s}}(m_1)\times {\mathrm{LWE}}_{\mathbf{s}}(m_2)\to {\mathrm{LWE}}_{\mathbf{s}}(m_1+m_2)$$

Let $\mathbf{s}$ be a LWE key, let $m_1,m_2\in {\mathbb{Z}}_q$ be two messages and let $L_1=({\mathbf{a}}_1,b_1)$ and $L_2=({\mathbf{a}}_2,b_2)$ be encryptions of $m_1$ and $m_2$ respectively.

By definition, $\mathrm{CAdd}(L_1,L_2)$ should be equal to a ciphertext $L_{\mathrm{sum}}$ that is an encryption of $m_1+m_2$.

How can we obtain $L_{\mathrm{sum}}$ from the inputs $L_1$ and $L_2$?

It turns out that all we have to do is add the coefficients of $L_1$ and $L_2$:

$$\mathrm{CAdd}(L_1,L_2):=({\mathbf{a}}_1+{\mathbf{a}}_2,b_1+b_2)$$

To prove that $L_{\mathrm{sum}}=\mathrm{CAdd}(L_1,L_2)$ is indeed an encryption of $m_1+m_2$, let’s decrypt it:

In summary:

This proves that $L_{\mathrm{sum}}$ is an encryption of $m_1+m_2$ with noise $e_1+e_2$.

Later in this post we will also use the analogous homomorphic subtraction function $\mathrm{CSub}$:

$$\mathrm{CSub}:{\mathrm{LWE}}_{\mathbf{s}}(m_1)\times {\mathrm{LWE}}_{\mathbf{s}}(m_2)\to {\mathrm{LWE}}_{\mathbf{s}}(m_1-m_2)$$

Here are concrete implementations of $\mathrm{CAdd}$ and $\mathrm{CSub}$:

def lwe_add(
    ciphertext_left: LweCiphertext,
    ciphertext_right: LweCiphertext) -> LweCiphertext:
    """Homomorphic addition evaluation.

       If ciphertext_left is an encryption of m_left and ciphertext_right is
       an encryption of m_right then return an encryption of
       m_left + m_right.
    """
    return LweCiphertext(
        ciphertext_left.config,
        np.add(ciphertext_left.a, ciphertext_right.a, dtype=np.int32),
        np.add(ciphertext_left.b, ciphertext_right.b, dtype=np.int32))

def lwe_subtract(
    ciphertext_left: LweCiphertext,
    ciphertext_right: LweCiphertext) -> LweCiphertext:
    """Homomorphic subtraction evaluation.

       If ciphertext_left is an encryption of m_left and ciphertext_right is
       an encryption of m_right then return an encryption of
       m_left - m_right.
    """
    return LweCiphertext(
        ciphertext_left.config,
        np.subtract(ciphertext_left.a, ciphertext_right.a, dtype=np.int32),
        np.subtract(ciphertext_left.b, ciphertext_right.b, dtype=np.int32))

Here is an example of homomorphic addition:

key = lwe.generate_lwe_key(config.LWE_CONFIG)

# Encode the values 3 and -1 as LWE plaintexts
plaintext_a = lwe.lwe_encode(3)
plaintext_b = lwe.lwe_encode(-1)

# Encrypt both plaintexts
ciphertext_a = lwe.lwe_encrypt(plaintext_a, key)
ciphertext_b = lwe.lwe_encrypt(plaintext_b, key)

# Homomorphically add the ciphertexts.
ciphertext_sum = lwe.lwe_add(ciphertext_a, ciphertext_b)

# Decrypt the ciphertext_sum and then decode it. The result should
# be equal to 3 + (-1) = 2
decrypted = lwe.lwe_decrypt(ciphertext_sum, key)
decoded = lwe.lwe_decode(decrypted)
assert decoded == 2

Homomorphic Multiplication By Plaintext

In this section we’ll implement the homomorphic multiplication by plaintext function:

$$\mathrm{PMul}(c,\cdot ):{\mathrm{LWE}}_{\mathbf{s}}(m)\to {\mathrm{LWE}}_{\mathbf{s}}(c\cdot m)$$

Let $\mathbf{s}$ be a LWE key, let $c,m\in {\mathbb{Z}}_q$ be two messages and let $L=(\mathbf{a},b)$ be an encryption of $m$.

By definition, $\mathrm{PMul}(c,L)$ should be equal to a ciphertext $L_{\mathrm{prod}}$ that is an encryption of $c\cdot m$.

Inspired by the previous section, we can attempt to implement $\mathrm{PMul}$ by element wise multiplication of the scalar $c$ with the vector $L=(\mathbf{a},b)$:

$$\mathrm{PMul}(c,L):=c\cdot L=(c\cdot \mathbf{a},c\cdot b)$$

As before, we can verify that this is correct by decrypting $L_{\mathrm{prod}}=\mathrm{PMul}(c,L)$:

This shows that the result of decrypting $L_{\mathrm{prod}}$ is the product $c\cdot m$ together with some noise that is equal to $c\cdot e$. If $c$ is small then the noise is small and so $\mathrm{PMul}(c,L)$ is a valid encryption of $c\cdot m$. We’ll analyze the noise more closely in the next section.

Here is an implementation of $\mathrm{PMul}$:

def lwe_plaintext_multiply(c: int, ciphertext: LweCiphertext) -> LweCiphertext:
    """Homomorphically multiply an LWE ciphertext with a plaintext integer."""
    return LweCiphertext(
        ciphertext.config,
        np.multiply(c, ciphertext.a, dtype=np.int32),
        np.multiply(c, ciphertext.b, dtype=np.int32),
    )

Noise Analysis

In this section we’ll analyze the effects of homomorphic operations on ciphertext noise.

Let $m_1$ and $m_2$ be LWE plaintexts. Let $L_i$ be an LWE encryption of $m_i$ with noise $e_i$. By equation $\text{2}$, $\mathrm{CAdd}(L_1,L_2)$ is an encryption of $m_1+m_2$ with noise $e_1+e_2$. This means that when we homomorphically add two ciphertexts, the noise in each of the inputs gets added to the result.

For example, let’s see what happens when we take an encryption of $0$ and homomorphically add it to itself 10 times. We’ll repeat the entire process 1000 times and plot the ciphertext error distribution before and after the homomorphic addition:

key = lwe.generate_lwe_key(config.LWE_CONFIG)
plaintext_zero = lwe.LwePlaintext(0)

initial_errors = []
addition_errors = []

for _ in range(1000):
    # Encrypt the plaintext and record the ciphertext error.
    ciphertext_zero = lwe.lwe_encrypt(plaintext_zero, key)
    initial_errors.append(lwe.lwe_decrypt(ciphertext_zero, key).message)

    # Homomorphically add the ciphertext to itself 10 times.
    ciphertext_sum = ciphertext_zero
    for _ in range(10):
        ciphertext_sum = lwe.lwe_add(ciphertext_sum, ciphertext_zero)

    # Record the error of the ciphertext sum.
    addition_errors.append(lwe.lwe_decrypt(ciphertext_sum, key).message)

The graph on the left shows the distribution of initial_errors which records the errors in the initial encryptions of $0$. The graph on the right shows the distribution of addition_errors which contains the ciphertext errors after 10 homomorphic additions. As expected, the noise on the right is about 10 times larger.

The maximum error in the graph on the right is around 5000 which is still significantly smaller than the maximal acceptable error of $2^{28}$. However, after $2^{20}$ homomorphic additions we’d eventually surpass that limit and no longer be able to accurately decode messages.

A major goal for the rest of this post is to develop a homomorphic operation whose output noise is independent of the input noise. This will make it possible to compose an arbitrary number of homomorphic operations, without running into the noise issue above.

Trivial Encryption

Let $m$ be an LWE plaintext and let $\mathbf{s}$ be an LWE encryption key. Consider the tuple:

where $\mathbf{0}$ is a length $n$ vector of zeroes. We claim that $L$ is a valid LWE encryption of $m$ with no noise. Indeed, the decryption of $L$ is exactly equal to $m$:

The ciphertext $L$ is called the trivial encryption of $m$.

Here is our library implementation:

def lwe_trivial_ciphertext(plaintext: LwePlaintext, config: LweConfig):
    """Generate a trivial encryption of the plaintext."""
    return LweCiphertext(
        config=config,
        a=np.zeros(config.dimension, dtype=np.int32),
        b=plaintext.message,
    )

As an example of why this is useful, let $m_1$ be an LWE plaintext and let $L_2\in {\mathrm{LWE}}_{\mathbf{s}}(m_2)$ be an LWE encryption of $m_2$. How can we homomorphically add $m_1$ to $L_2$ to produce an encryption of $m_1+m_2$?

In section Homomorphic Addition we implemented the function $\mathrm{CAdd}$ which homomorphically adds two LWE ciphertexts. We cannot directly apply $\mathrm{CAdd}$ since we are trying to add the plaintext $m_1$ to the ciphertext $L$. Instead, we can first convert $m_1$ to its trivial encryption $L_1$ and then compute $\mathrm{CAdd}(L_1,L_2)$.

Homomorphic NAND Revisited

In the previous section we introduced the LWE encryption scheme together with some basic homomorphic operations. This will allow us to refine our definition of the homomorphic NAND gate from section A Fully Homomorphic Nand Gate and give an overview of our implementation strategy.

Definition

In this section we’ll introduce an encoding of boolean values as LWE messages and precisely define the homomorphic NAND function.

We’ll use the $\mathrm{Encode}$ function from section Message Encoding to represent boolean values as LWE plaintexts. Specifically, we’ll represent $\mathrm{True}$ by $\mathrm{Encode}(2)$ and represent $\mathrm{False}$ by $\mathrm{Encode}(0)$.

Let $b_0$ and $b_1$ denote two booleans with the above representation. The homomorphic NAND gate $\mathrm{CNAND}$ has the signature:

In other words, if $L_0\in {\mathrm{LWE}}_{\mathbf{s}}(b_0)$ is an LWE encryption of $b_0$ and $L_1\in {\mathrm{LWE}}_{\mathbf{s}}(b_1)$ is an LWE encryption of $b_1$ then $\mathrm{CNAND}(L_0,L_1)$ is an LWE encryption of $\mathrm{NAND}(b_0,b_1)$.

Another important requirement for $\mathrm{CNAND}$ is that the noise of the output ciphertext $\mathrm{CNAND}(L_0,L_1)$ should be bounded and independent of the noise of the inputs $L_0$ and $L_1$. This property will make it possible to compose an arbitrary number of homomorphic NAND gates without suffering from the noise explosion issue that we saw in section Noise Analysis.

Here are the functions we’ll use to encode booleans as LWE plaintexts and to decode plaintexts back to booleans. Note that we’re using the encode and decode functions defined here.

def encode_bool(b: bool) -> np.int32:
    """Encode a bit as an int32."""
    return encode(2 * int(b))


def decode_bool(i: np.int32) -> bool:
    """Decode an int32 to a bool."""
    return bool(decode(i) / 2)

def lwe_encode_bool(b: bool) -> LwePlaintext:
    """Encode a boolean as an LWE plaintext."""
    return LwePlaintext(utils.encode_bool(b))


def lwe_decode_bool(plaintext: LwePlaintext) -> bool:
    """Decode an LWE plaintext to a boolean."""
    return utils.decode_bool(plaintext.message)

The signature of our homomorphic NAND function is:

def lwe_nand(
    lwe_ciphertext_left: lwe.LweCiphertext,
    lwe_ciphertext_right: lwe.LweCiphertext,
    bootstrap_key: bootstrap.BootstrapKey,
) -> lwe.LweCiphertext:
    """Homomorphically evaluate the NAND function.

    Suppose that lwe_ciphertext_left is an LWE encryption of
    lwe_encode_bool(b_left) and lwe_ciphertext_right is an LWE encryption
    lwe_encode_bool(b_right). Then the the output is an LWE encryption
    lwe_encode_bool(NAND(b_left, b_right)).
    """
    pass

As we’ll see later, bootstrap_key is a public key that untrusted parties can use to homomorphically evaluate functions.

Here is an example:

# Generate a private LWE encryption key.
lwe_key = lwe.generate_lwe_key(config.LWE_CONFIG)

# Generate a public bootstrapping key.
gsw_key = gsw.convert_lwe_key_to_gsw(lwe_key, config.GSW_CONFIG)
bootstrap_key = bootstrap.generate_bootstrap_key(lwe_key, gsw_key)

# Encode two boolean values as LWE plaintexts.
plaintext_0 = lwe.lwe_encode_bool(False)
plaintext_1 = lwe.lwe_encode_bool(True)

# Encrypt the plaintexts.
ciphertext_0 = lwe.lwe_encrypt(plaintext_0, lwe_key)
ciphertext_1 = lwe.lwe_encrypt(plaintext_1, lwe_key)

# Homomorphically compute the NAND function on the inputs.
ciphertext_nand = nand.lwe_nand(
    ciphertext_0, ciphertext_1, bootstrap_key
)

# Decrypt the homomorphic NAND result with the LWE key.
plaintext_nand = lwe.lwe_decrypt(ciphertext_nand, lwe_key)

# Decode the LWE plaintext back to a bool.
boolean_nand = lwe.lwe_decode_bool(plaintext_nand)

# The result should be equal to NAND(False, True) = True
assert boolean_nand == True

Implementation Strategy

The remainder of this post will be dedicated to implementing lwe_nand. In this section we’ll discuss our high level strategy.

Recall that our encoding function $\mathrm{Encode}$ maps values from ${\mathbb{Z}}_8=[-4,4)$ to ${\mathbb{Z}}_q=[-2^{31},2^{31})$ and is defined by $\mathrm{Encode}(i):=i\cdot 2^{29}$:

We’ll start by expressing NAND in terms of elementary operations on ${\mathbb{Z}}_q$.

As before, we will identify $\mathrm{True}$ with $\mathrm{Encode}(2)$ and $\mathrm{False}$ with $\mathrm{Encode}(0)$. Let $b_0,b_1\in \{\mathrm{Encode}(0),\mathrm{Encode}(2)\}$ be two boolean values and consider the expression:

$$F(b_0,b_1)=\mathrm{Encode}(-3)-b_0-b_1$$

In terms of the diagram above, we start at $\mathrm{Encode}(-3)=-3\cdot 2^{29}$ and move two dots counter clockwise for each $b_i$ that is “true”. Here are the four possible values (modulo $q=2^{32}$) that this expression can take:

Note that $-2\cdot 2^{29}<F(b_0,b_1)\le 2\cdot 2^{29}$ if and only if $b_0=b_1=\mathrm{Encode}(2)$. We can therefore upgrade $F(b_0,b_1)$ to a NAND function by composing it with the step function $\mathrm{Step}(x)$ which is defined on ${\mathbb{Z}}_q$ as follows:

Here’s what happens when we apply $\mathrm{Step}(x)$ to $F(b_0,b_1)$:

It is evident from the table that

In summary, we’ve expressed the NAND function in terms of two operations on ${\mathbb{Z}}_q$: subtraction and the step function.

In section Homomorphic Addition we already implemented a homomorphic subtraction function $\mathrm{CSub}$. Therefore, all that remains is to implement a homomorphic step function. In the remainder of this post we will develop the bootstrapping function $\mathrm{Bootstrap}$ which is essentially a homomorphic step function that also has bounded output noise.

We can then use $\mathrm{CSub}$ and $\mathrm{Boostrap}$ to implement $\mathrm{CNAND}$:

$$\mathrm{CNAND}(L_0,L_1)=\mathrm{Bootstrap}(\mathrm{CSub}(\mathrm{CSub}(\mathrm{Encode}(-3),L_0),L_1))$$

Here is the python implementation:

import numpy as np

from tfhe import bootstrap, lwe


def lwe_nand(
    lwe_ciphertext_left: lwe.LweCiphertext,
    lwe_ciphertext_right: lwe.LweCiphertext,
    bootstrap_key: bootstrap.BootstrapKey,
) -> lwe.LweCiphertext:
    """Homomorphically evaluate the NAND function.

    Suppose that lwe_ciphertext_left is an LWE encryption of an encoding of the
    boolean b_left and lwe_ciphertext_right is an LWE encryption of an encoding
    of the boolean b_right. Then the the output is an LWE encryption of an encoding
    of NAND(b_left, b_right).
    """
    # Compute an LWE encryption of: encode(-3) - b_left - b_right
    # First create a trivial encryption of encode(-3)
    initial_lwe_ciphertext = lwe.lwe_trivial_ciphertext(
        plaintext=lwe.lwe_encode(-3),
        config=lwe_ciphertext_left.config,
    )

    # Homomorphically subtract lwe_ciphertext_left and lwe_ciphertext_right
    lwe_ciphertext = lwe.lwe_subtract(
        initial_lwe_ciphertext, lwe_ciphertext_left
    )
    lwe_ciphertext = lwe.lwe_subtract(
        test_lwe_ciphertext, lwe_ciphertext_right
    )

    # Bootstrap lwe_ciphertext to output encode_bool(False) or
    # encode_bool(True).
    return bootstrap.bootstrap(
        lwe_ciphertext, bootstrap_key, scale=utils.encode_bool(True)
    )

Bootstrapping

Definition

In the context of TFHE, the $\mathrm{Bootstrap}$ function is a homomorphic version of the $\mathrm{Step}$ function defined in equation $\text{3}$.

More precisely, let $m\in {\mathbb{Z}}_q$ be an LWE message. The signature of $\mathrm{Bootstrap}$ is:

In other words, $\mathrm{Bootstrap}$ takes as input an LWE encryption of a message $m$ and outputs an LWE encryption of $\mathrm{Step}(m)$.

The other key property of $\mathrm{Bootstrap}$ is that the noise distribution of its output ciphertext is independent of the noise of the input. This property is what will allow us to compose an arbitrary number of homomorphic NAND functions without an explosion of the ciphertext noise.

Here is the declaration of the $\mathrm{Bootstrap}$ function:

def bootstrap(
    lwe_ciphertext: lwe.LweCiphertext,
    bootstrap_key: BootstrapKey,
    scale: np.int32,
) -> lwe.LweCiphertext:
    """Bootstrap the LWE ciphertext.

    Suppose that lwe_ciphertext is an encryption of the int32 i.
    If -2^30 < i <= 2^30 then return an LWE encryption of the scale argument.
    Otherwise return an LWE encryption of 0. In both cases the ciphertext noise
    will be bounded and independent of the lwe_ciphertext noise.
    """
    pass

The bootstrap_key argument will be explained later in this post. The scale parameter is the non zero output value of the step function. Our definition of $\mathrm{Step}$ above corresponds to scale = utils.encode(2).

Noise Properties

As mentioned in the previous section, a key property of the bootstrap function is that it has bounded output noise. In this section we’ll explore this property in more detail through an example.

Let $m_0=\mathrm{Encode}(0)$ and $m_1=\mathrm{Encode}(3)$ be two LWE messages. Let $L_0={\mathrm{Encrypt}}_{\mathbf{s}}(m_0)$ be an encryption of $m_0$ and $L_1={\mathrm{Encrypt}}_{\mathbf{s}}(m_1)$ and encryption of $m_1$.

Suppose we homomorphically multiply $L_0$ by $2^{20}$ and add the result to $L_1$:

$$L=\mathrm{CAdd}(L_1,\mathrm{PMul}(2^{20},L_0))$$

As we saw in section Homomorphic Multiplication By Plaintext, $\mathrm{PMul}(2^{20},L_0)$ is an encryption of $2^{20}\cdot 0=0$. Therefore, $L$ is an encryption of $\mathrm{Encode}(3)+0=\mathrm{Encode}(3)$. Furthermore, as we saw in section Noise Analysis, we the expect noise distribution of $L$ to roughly have a standard deviation of $2^{20}\cdot 2^7=2^{27}$.

The following program computes the ciphertexts $L$ and $\mathrm{Bootstrap}(L)$ 1000 times so that we can compare the distributions of the decryptions ${\mathrm{Dec}}_{\mathbf{s}}(L)$ and ${\mathrm{Dec}}_{\mathbf{s}}(\mathrm{Bootstrap}(L))$:

from tfhe import bootstrap, gsw, lwe, utils

lwe_key = lwe.generate_lwe_key(config.LWE_CONFIG)
gsw_key = gsw.convert_lwe_key_to_gsw(lwe_key, config.GSW_CONFIG)
bootstrap_key = bootstrap.generate_bootstrap_key(lwe_key, gsw_key)

plaintext_0 = lwe.lwe_encode(0)
plaintext_3 = lwe.lwe_encode(3)

decryptions = []
bootstrap_decryptions = []

for _ in range(1000):
    ciphertext_0 = lwe.lwe_encrypt(plaintext_0, lwe_key)
    ciphertext_3 = lwe.lwe_encrypt(plaintext_3, lwe_key)

    ciphertext = lwe.lwe_add(
        ciphertext_3, lwe.lwe_plaintext_multiply(2**20, ciphertext_0))

    bootstrap_ciphertext = bootstrap.bootstrap(
        ciphertext, bootstrap_key, scale=utils.encode(2)
    )

    decryptions.append(lwe.lwe_decrypt(ciphertext, lwe_key).message)
    bootstrap_decryptions.append(
        lwe.lwe_decrypt(bootstrap_ciphertext, lwe_key).message)

Here is a comparison of the array decryptions which holds decryptions of $L$ and the array bootstrap_decryptions which holds decryptions of $\mathrm{Bootstrap}(L)$:

As expected, the distribution of decryptions of $L$ is centered at $\mathrm{Encode}(3)=3\cdot 2^{29}$ with a standard deviation of $2^{27}$.

After bootstrapping, the distribution of decryptions is centered at

$$\mathrm{Step}(\mathrm{Encode}(3))=\mathrm{Encode}(2)=2\cdot 2^{29}$$

Furthermore, the distribution clearly is less noisy after bootstrapping. Indeed, the standard deviation of $\mathrm{Bootstrap}(L)$ is $2^{25}$ which is less than the standard deviation of $L$!

Implementation Strategy

The rest of this post will build towards an implementation of $\mathrm{Bootstrap}$. The implementation will rely on an extension of LWE called Ring LWE where messages can be polynomials rather than scalars. The general idea is that we will express $\mathrm{Step}$ in terms of polynomial multiplication, and then use homomorphic polynomial multiplication to derive a homomorphic version of $\mathrm{Step}$.

If you prefer to get a high level picture of the implementation before diving into all the details, then it would make sense to start with the following sections:

1. Ring LWE
2. Blind Rotation Definition
3. Sample Extraction Definition
4. Bootstrapping Implementation

Ring LWE

Introduction

Ring LWE (RLWE) is a variation of LWE in which messages are polynomials rather than scalars. As mentioned in the previous section, the RLWE encryption scheme will be an important ingredient in our bootstrapping implementation.

In the next section we’ll define the message space of RLWE more precisely. Then we’ll define the RLWE encryption scheme.

Negacyclic Polynomials

The message space of the RLWE scheme is the ring of polynomials

$${\mathbb{Z}}_q[x]/(x^n+1)$$

In this section we will describe this polynomial ring.

First, ${\mathbb{Z}}_q[x]$ denotes the ring of polynomials with coefficients in ${\mathbb{Z}}_q$. As before, we will assume that $q=2^{32}$ and identify ${\mathbb{Z}}_q$ with signed 32 bit integers. In this context ${\mathbb{Z}}_q[x]$ denotes the ring of polynomials integer coefficients.

Here is an example of an element in ${\mathbb{Z}}_q[x]$:

$$f(x)=1+2x-5x^3$$

We call ${\mathbb{Z}}_q[x]$ a Ring because we can add and multiply elements. For example, if $f(x)=1+2x-5x^3$ and $g(x)=1+x$ then $f(x)+g(x)=2+3x-5x^3$ and $f(x)\cdot g(x)=1+3x+2x^2-5x^3-5x^4$.

The highest power of $x$ in a polynomial is called the degree. For example, the degree of $f(x)$ is $3$ and the degree of $g(x)$ is $1$. Polynomials in ${\mathbb{Z}}_q[x]$ can have arbitrarily high degrees.

We now turn to the ring ${\mathbb{Z}}_q[x]/(x^n+1)$. The denominator $x^n+1$ plays a similar role to the denominator in ${\mathbb{Z}}_q=\mathbb{Z}/q\mathbb{Z}$. Two integers are considered to be equal modulo $q$ if they differ by a multiple of $q$. Similarly, two polynomials are considered to be equal modulo $x^n+1$ if they differ by a multiple of $x^n+1$.

${\mathbb{Z}}_q[x]/(x^n+1)$ is defined to be the ring of polynomials modulo $x^n+1$.

As an important special case, $x^n=-1(\mathrm{mod}{x}^n+1)$. Therefore, if we are given a polynomial with a degree larger than $n$, we can find it’s representative modulo $x^n+1$ by replacing $x^n$ with $-1$ as many times as necessary. For example, if $n=4$ then we have the following equivalences modulo $x^4+1$:

Note that as monomials reach $x^4$ they loop back to $1$ but with a negative sign. For this reason polynomials of this form are sometimes called negacyclic.

Now let’s see an example of multiplication in ${\mathbb{Z}}_q[x]/(x^4+1)$. Let $f(x)=1+x^3$ and $g(x)=x$ be elements of ${\mathbb{Z}}_q[x]/(x^4+1)$. Their product is:

$$f(x)\cdot g(x)=x+x^4=x-1=-1+x(\mathrm{mod}{x}^4+1)$$

Here is some negacyclic polynomial code that will be used later:

import numpy as np
import dataclasses


@dataclasses.dataclass
class Polynomial:
    """A polynomial in the ring Z_q[x] / (x^N + 1)"""
    N: int
    coeff: np.ndarray # Polynomial coefficients f_0, f_1, ..., f_{N-1}


def polynomial_constant_multiply(c: int, p: Polynomial) -> Polynomial:
    return Polynomial(N=p.N, coeff=np.multiply(c, p.coeff, dtype=np.int32))


def polynomial_multiply(p1: Polynomial, p2: Polynomial) -> Polynomial:
    """Multiply two negacyclic polynomials.

    Note that this is not an optimal implementation.
    See
    https://www.jeremykun.com/2022/12/09/negacyclic-polynomial-multiplication/
    for a more efficient version which uses FFTs.
    """
    N = p1.N

    # Multiply and pad the result to have length 2N-1.
    # Note that the polymul function expects the coefficients to be from highest
    # to lowest degree so we reverse our coefficients before and after using it.
    prod = np.polymul(p1.coeff[::-1], p2.coeff[::-1])[::-1]
    prod_padded = np.zeros(2 * N - 1, dtype=np.int32)
    prod_padded[: len(prod)] = prod

    # Use the relation x^N = -1 to obtain a polynomial of degree N-1
    result = prod_padded[:N]
    result[:-1] -= prod_padded[N:]
    return Polynomial(N=N, coeff=result)


def polynomial_add(p1: Polynomial, p2: Polynomial) -> Polynomial:
    return Polynomial(N=p1.N, coeff=np.add(p1.coeff, p2.coeff, dtype=np.int32))


def polynomial_subtract(p1: Polynomial, p2: Polynomial) -> Polynomial:
    return Polynomial(
        N=p1.N, coeff=np.subtract(p1.coeff, p2.coeff, dtype=np.int32)
    )


def zero_polynomial(N: int) -> Polynomial:
    return Polynomial(N=N, coeff=np.zeros(N, dtype=np.int32))


def build_monomial(c: int, i: int, N: int) -> Polynomial:
    """Build a monomial c*x^i in the ring Z[x]/(x^N + 1)"""
    coeff = np.zeros(N, dtype=np.int32)

    # Find k such that: 0 <= i + k*N < N
    i_mod_N = i % N
    k = (i_mod_N - i) // N

    # If k is odd then the monomial picks up a negative sign since:
    # x^i = (-1)^k * x^(i + k*N) = (-1)^k * x^(i % N)
    sign = 1 if k % 2 == 0 else -1

    coeff[i_mod_N] = sign * c
    return Polynomial(N=N, coeff=coeff)

The RLWE Encryption Scheme

In this section we will define the RLWE Encryption Scheme which is very similar to the LWE encryption scheme but with messages in ${\mathbb{Z}}_q[x]/(x^n+1)$ rather than ${\mathbb{Z}}_q$.

A secret key in RLWE is a polynomial in ${\mathbb{Z}}_q[x]/(x^n+1)$ with random binary coefficients. For example, if $n=4$ then a secret key may look like:

To encrypt a message $m(x)\in {\mathbb{Z}}_q[x]/(x^n+1)$ with the secret key $s(x)$ we first sample a polynomial $a(x)\in {\mathbb{Z}}_q[x]$ with uniformly random coefficients in ${\mathbb{Z}}_q$ and an error polynomial $e(x)\in {\mathbb{Z}}_q[x]$ with small error coefficients sampled from ${\mathcal{N}}_q$. The encryption of $m(x)$ by $s(x)$ is then given by the pair:

To decrypt a ciphertext $(a(x),b(x))$ we compute:

Similarly to LWE, the encryption function is not deterministic and so each message has many valid encryptions. The set of valid encryptions of a message $m(x)$ with the key $s(x)$ will be denoted ${\mathrm{RLWE}}_{s(x)}(m(x))$.

Here is our implementation of the RLWE scheme:

import dataclasses

import numpy as np

from tfhe import lwe, polynomial, utils
from tfhe.polynomial import Polynomial


@dataclasses.dataclass
class RlweConfig:
    degree: int  # Messages will be in the space Z[X]/(x^degree + 1)
    noise_std: float  # The std of the noise added during encryption.


@dataclasses.dataclass
class RlweEncryptionKey:
    config: RlweConfig
    key: Polynomial


@dataclasses.dataclass
class RlwePlaintext:
    config: RlweConfig
    message: Polynomial


@dataclasses.dataclass
class RlweCiphertext:
    config: RlweConfig
    a: Polynomial
    b: Polynomial


def generate_rlwe_key(config: RlweConfig) -> RlweEncryptionKey:
    return RlweEncryptionKey(
        config=config,
        key=Polynomial(
            N=config.degree,
            coeff=np.random.randint(
                low=0, high=2, size=config.degree, dtype=np.int32
            ),
        ),
    )

def rlwe_encrypt(
    plaintext: RlwePlaintext, key: RlweEncryptionKey
) -> RlweCiphertext:
    a = Polynomial(
        N=key.config.degree,
        coeff=utils.uniform_sample_int32(size=key.config.degree),
    )
    noise = Polynomial(
        N=key.config.degree,
        coeff=utils.gaussian_sample_int32(
            std=key.config.noise_std, size=key.config.degree
        ),
    )

    b = polynomial.polynomial_add(
        polynomial.polynomial_multiply(a, key.key), plaintext.message
    )
    b = polynomial.polynomial_add(b, noise)

    return RlweCiphertext(config=key.config, a=a, b=b)


def rlwe_decrypt(
    ciphertext: RlweCiphertext, key: RlweEncryptionKey
) -> RlwePlaintext:
    message = polynomial.polynomial_subtract(
        ciphertext.b, polynomial.polynomial_multiply(ciphertext.a, key.key)
    )
    return RlwePlaintext(config=key.config, message=message)

We’ll use the following RLWE parameters in this post:

RLWE_CONFIG = rlwe.RlweConfig(degree=1024, noise_std=2 ** (-24))

Message Encoding

As with LWE, after decrypting a ciphertext $m(x)\in {\mathrm{RLWE}}_{s(x)}(m(x))$ we get the original message $m(x)$ together with a small amount of noise $e(x)$. To achieve noiseless decryptions we’ll extend the $\mathrm{Encode}$ and $\mathrm{Decode}$ functions from Message Encoding to polynomials by encoding and decoding each individual coefficient.