Part 3: Noise Growth Problem & Gentry's Bootstrapping | Building Blocks of FHE

Craig Gentry revolutionized the field of cryptography by introducing Fully Homomorphic Encryption (FHE), a groundbreaking concept that allows computations to be performed directly on encrypted data. This remarkable innovation ensures that data remains secure even during processing, unlocking unprecedented potential for privacy in cloud computing and data analytics.

Notion of Noise in Homomorphic Encryption

Why Do We Need Noise?

Noise is used to make it difficult for adversaries to decrypt the encrypted data, even if they can see the ciphertext. The noise adds randomness, preventing attackers from distinguishing between different encrypted messages (ciphertexts) easily. So it increases the computational complexity required for potential attackers to recover the plaintext without the secret key.

Let us consider Ring-LWE-based encryption, for the sake of simplicity, in simpler terms:

$$ c = m + 2r + e (mod 2) $$

where $m, r, e$ are polynomials.

If we had no noise,

$$ Dec(c_1 + c_2) = Dec(c_1) + Dec(c_2) $$

$$ Dec(c_1 \cdot c_2) = Dec(c_1) \cdot Dec(c_2) $$

We would have a perfect ring homomorphism, but there is a problem!

Problem: The scheme would not be secure and the polynomial degree would increase after each multiplication.

Noise Growth

Let us try to understand how fast noise grows during arithmetic operations.

Noise Growth in Addition

Let’s start with addition. Assume that

$$ c_1(s) \approx_\epsilon m_1 (mod 2) $$

$$ c_2(s) \approx_\epsilon m_2 (mod 2) $$

Then

$$ c(s) \approx_{2\epsilon} m (mod 2) $$

where $m = m_1 + m_2$

As you may have noticed, the noise doubles during addition.

Problem: Noise grows after every single addition process.

Noise Growth in Multiplication

Now, we will inspect noise growth in multiplication for given:

$$ c_1(s) \approx_\epsilon m_1 (mod 2) $$

$$ c_2(s) \approx_\epsilon m_2 (mod 2) $$

Then we have

$$ c(s) = c_1(s) \cdot c_2(s) $$

$$ c(s) = (m_1 + 2r_1 + e_1) \cdot (m_2 + 2r_2 + e_2) $$

$$ c(s) = m_1 \cdot m_2 + 2r + (e_1 \cdot c_2(s) + e_2 \cdot c_1(s)) $$

Hence,

$$ c(s) \approx_{2(n+1)\epsilon} m_1 \cdot m_2 (mod \ 2) $$

Problem: Noise grows even faster.

Noise Growth Summary

Addition: $ \epsilon \rightarrow 2\epsilon $

Multiplication: $ \epsilon \rightarrow poly(n) \cdot \epsilon $

If the depth of the circuit is $d$, then

$$ \epsilon \rightarrow poly(n)^d \cdot \epsilon $$

Therefore, addition and (especially) multiplication increase the noise in a ciphertext.

‍What Is an FHE Scheme?

What Does “Homomorphic” Mean?

Fully homomorphic encryption (FHE) fundamentally relies on leveraging mathematical constructs enabling operations on encrypted data (ciphertext) to yield identical outcomes as if these operations were executed on the initial unencrypted data (plaintext) when decrypted.

The name comes from a mathematical notion: homomorphism!

Definition: Let $G$ and $H$ be groups and $f: G \rightarrow H$ be a mapping (function). $f$ is called a group homomorphism if

$$f(g_1 *_G g_2) = f(g_1) *_H f(g_2)$$

for all $g_1, g_2 \in G$ where $*_G$ and $*_H$ denote the group operations of $G$ and $H$, respectively.

Some Fundamental Definitions

Circuit: In computer science and cryptography, a circuit is a mathematical model that represents computation. Structurally, it is a directed acyclic graph (DAG) where the nodes, or gates, represent logical or arithmetic functions like AND, OR, NOT, and XOR. These nodes process inputs to produce outputs, while the edges, or wires, direct the flow of data between gates, carrying the output of one gate as the input to another. Circuits consist of input nodes, which lack incoming edges and serve as primary data inputs, and output nodes, which provide the computation's final results. The complexity of a circuit is measured by its size (total number of gates) and depth (longest path from any input to output). Circuits can be classified as Boolean (handling logical operations) or arithmetic (handling numerical calculations). In cryptography, circuits are essential for securely modeling computations in homomorphic encryption, where circuit depth and size significantly affect the computational expense of securely processing encrypted data.

‍Homomorphic Encryption: $E$ is homomorphic for circuits in $C_E$ if $E$ is correct for $C_E$ and $Dec_E$ can be expressed as a circuit $D_E$ of size $poly(\lambda)$.

‍Fully Homomorphic Encryption: $E$ is fully homomorphic if it is homomorphic for all circuits.

What Does an FHE Scheme Look Like?

A homomorphic public key encryption scheme $E$ has four algorithms $KeyGen_E$, $Enc_E$, $Dec_E$$, and an additional algorithm $Eval_E$ that takes as input the public key $pk$, a circuit $C$ from a permitted set $C_E$ of circuits, and a tuple of ciphertexts $ \psi = \langle \psi_1, \psi_2, ..., \psi_n \rangle $; it outputs a ciphertext $\psi$.

The computational complexity of all of these algorithms must be probabilistic polynomial time (PPT) algorithms (in a security parameter $\lambda$). $E$ is correct for circuits in $C_E$ if, for any key-pair $(sk, pk)$ output by $KeyGen_E(\lambda)$, any circuit $C \in C_E$, any plaintexts $\pi_1, \pi_2, ..., \pi_n$, and any ciphertexts $\Psi = \langle \psi_1, \psi_2, ..., \psi_n \rangle$ with $\psi_i \leftarrow Enc_E(pk, \pi_i)$, it is the case that:

$$ \psi \leftarrow Eval_E(pk, C, \Psi) \implies C(\pi_1, ..., \pi_n) = Dec_E(sk, \psi) $$

Let’s break down the symbols and terminology used:

• $\psi$: The result obtained by evaluating a function on the encrypted data.
• $Eval_E$: The homomorphic evaluation function for the encryption scheme. This function allows computation to be done directly on encrypted data without needing to decrypt it first.
• $pk$: The public key used to encrypt data and to perform homomorphic evaluation.
• $sk$: The secret key used to decrypt data.
• $C$: The circuit to be performed homomorphically on the encrypted data.
• $\Psi$: The ciphertexts of the encrypted inputs.
• $Dec_E$: The decryption function for the encryption scheme.

Final logical implication can be interpreted as follows:

• The expression $\psi \leftarrow Eval_E(pk, C, \Psi)$ means that $\psi$, the result of evaluating the function $C$ on the encrypted data $\Psi$, is obtained using the homomorphic evaluation function $Eval_E$.
• The implication asserts that if you perform a homomorphic evaluation using $Eval_E$ to compute $C$ on encrypted inputs $\Psi$, the decrypted result of this computation will yield the same output as directly evaluating the function $C$ on the corresponding plaintext inputs (represented as $(\pi_1, \pi_2, …, \pi_n)$).

Gentry’s Bootstrapping: Refreshing Ciphertexts

What Do We Mean by Refreshing Ciphertexts?

Until Craig Gentry, we had been only able to evaluate bounded depth functions because of the noise growth problem. However, we needed to find a way to control the noise to make it possible to remove the boundary.

In other words, we need a new ciphertext $c'$ that encrypts the same value but with less noise.

Normally, the best way to get rid of the noise is to decrypt the ciphertext. But, of course, this is not something we want, to preserve the essence of homomorphic encryption. That’s why we do something smarter instead: Bootstrapping!

The Idea of Bootstrapping

Let’s recall here that $E$ is homomorphic only for shallow circuits because the error vector grows with addition and (especially) multiplication operations; eventually it becomes so long that it becomes impossible to decrypt to the initial plaintext.

So the question to ask is: “Can we refresh a ciphertext whose error vector is almost too long, to obtain a new ciphertext whose error vector is shorter?”

The answer is yes! We can refresh a ciphertext by decrypting it homomorphically.

Gentry’s Bootstrapping Algorithm

Suppose we have an encryption scheme $E$ with plaintext space $P = \{0,1\}$. So we will be dealing with bits. Suppose also that we have a ciphertext $\psi_1$ that encrypts plaintext $\pi_1$ under a public key $pk_1$, which we want to refresh. So that we can decrypt our noisy ciphertext homomorphically, assume that we have the secret key $sk_1$ which corresponds to $pk_1$.

Then our “recryption” algorithm for ciphertext $\psi_1$ is as follows:

1. Encrypt bits of the secret key $sk_1$ under the new public key $pk_2$:

$$Enc_E(pk_2, sk_{1j}) = \overline{sk_{1j}}$$

2. Encrypt bits of the ciphertext $\psi_1$ under the new public key $pk_2$: 

$$Enc_E(pk_2, \psi_{1j}) = \overline{\psi_{1j}}$$

3. Evaluate the decryption circuit $D_E$ homomorphically to bits of the new ciphertext $\overline{psi_1}$ by using the encrypted secret key $\overline{sk_1}$:

$$Eval_E(pk_2, D_E, \langle \langle \overline{sk_{1j}} \rangle, \langle \overline{\psi_{1j}} \rangle \rangle) = \psi_2$$

With the base assumption of the fact that the decryption circuit is less noisy, we have a new ciphertext $\psi_2$ which has less noise.

Notice that the homomorphic decryption we performed removes the initial encryption layer along with the accumulated noise.

Conclusion

As we discussed, Gentry's bootstrapping algorithm uses homomorphic decryption to reset noise levels while retaining encryption, enabling encrypted data processing to move beyond the traditional limits imposed by noise growth. This breakthrough provides new opportunities for secure data analysis and cloud computing, laying a foundation for continued research and the development of more efficient FHE schemes.