D-2.11 Noise Bootstrapping

- Reference 1: Bootstrapping for BGV and BFV Revisited [14]

- Reference 2: Bootstrapping for HELib [15]

- Reference 3: A Note on Lower Digits Extraction Polynomial for Bootstrapping [16]

- Reference 4: Fully Homomorphic Encryption for Cyclotomic Prime Moduli [17]

In BFV, continuous ciphertext-to-ciphertext multiplication increases the noise in a multiplicative manner, and once the noise overflows the message bits, then the message gets corrupted. Bootstrapping is a process of resetting the grown noise.

D-2.11.1 High-level Idea

In this subsection, we will assume the plaintext modulus $t=p$, a prime number. Although $t$ can be generalized as $t=p^r$ where $r\in 𝕀$ and $r\ge 1$ (Summary D-2.3 in §D-2.3), we will explain BFV’s bootstrapping assuming $t=p$ for simplicity, and then generalize $t$ as $t=p^r$ in the end.

The core idea of the BFV bootstrapping is to homomorphically evaluate a special polynomial $G_{𝜀}(x)$, a digit extraction polynomial modulo $p^{𝜀}$ (for some positive integer $𝜀$), where the input to $G_{𝜀}(x)$ is a noisy plaintext value modulo $p^{𝜀}$ and the output is a noise-free plaintext value modulo $p^{𝜀}$, where the noise located at the least significant digits in a base-$p$ (prime) representation gets zeroed out. For example, $G_{𝜀}(3p^3+4p^2+6p+2)=3p^3+4p^2+6pmod{p}^{𝜀}$. Given the noise resides in the least significant $𝜀-1$ digits in base-$p$ representation, we can homomorphically recursively evaluate $G_{𝜀}(x)$ total $𝜀-1$ times in a row, which zeros out the least significant (base-$p$) $𝜀-1$ digits of input $x$. To homomorphically evaluate the noisy plaintext through $G_{𝜀}(x)mod{p}^{𝜀}$, we need to first switch the plaintext modulus from $t$ to $p^{𝜀}$, where $q\gg p^{𝜀}>p=t$. The larger $𝜀$ is, the more likely that the noise gets successfully zeroed out, but instead the computation overhead becomes larger. If $𝜀$ is small, the computation gets faster, but the digit-wise distance between the noise and the plaintext gets smaller, potentially corrupting the plaintext during bootstrapping, because removing the most significant noise digit may remove the least significant plaintext digit as well. Therefore, $𝜀$ should be chosen carefully.

The technical details of the BFV bootstrapping procedure are as follows. Suppose we have an RLWE ciphertext $(A,B)={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }M)modq$, where $A\cdot S+B=\mathrm{\Delta }M+E$, $\mathrm{\Delta }=\lfloor {\displaystyle \frac{q}{t}}\rfloor$ and $t=p$ (i.e., the plaintext modulus is a prime).

1.

Modulus Switch ($q\to p^{𝜀}$): Scale down the ciphertext modulus from $(A,B)modq$ to $\left(\lceil {\displaystyle \frac{p^{𝜀}}{q}}\cdot A\rfloor ,\lceil {\displaystyle \frac{p^{𝜀}}{q}}\cdot B\rfloor \right)=(A^{\prime },B^{\prime })mod{p}^{𝜀}$, where $p^{𝜀}\ll q$. The purpose of this modulus switch is to change the plaintext modulus to $p^{𝜀}$, which is required to use the digit extraction polynomial $G_{𝜀}(x)$ (because we need to represent the input to $G_{𝜀}(x)$ as a base-$p$ number in order to interpret it as a $mod{p}^{𝜀}$ value). Notice that ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}(\mathsf{\text{𝖼𝗍}}=(A^{\prime },B^{\prime }))=p^{𝜀-1}M+E^{\prime }$, where $E^{\prime }\approx {\displaystyle \frac{p^{𝜀}}{q}}\cdot E+\left(\lfloor {\displaystyle \frac{q}{p}}\rfloor \cdot {\displaystyle \frac{p^{𝜀}}{q}}-p^{𝜀-1}\right)\cdot M$ # the modulus switch error of $E\to E^{\prime }$ plus the modulus switch error of the plaintext’s scaling factor $\lfloor {\displaystyle \frac{q}{t}}\rfloor \to p^{𝜀-1}$

$$

2.

Homomorphic Decryption: Suppose we have the bootstrapping key ${\mathsf{\text{𝖱𝖫𝖾𝗏}}}_{S,\sigma }^{\beta ,l}(S)modq$, which is the secret key $S$ encrypted by $S$ (itself) modulo $q$. Using this encrypted secret key, we homomorphically decrypt $(A^{\prime },B^{\prime })$ as follows:

$A^{\prime }\cdot {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }S)+B^{\prime }$ # where ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }S)$ is a modulo-$q$ ciphertext that encrypts a modulo-$p^{𝜀}$ plaintext $S$ whose scaling factor ${\mathrm{\Delta }}^{\prime }={\displaystyle \frac{q}{p^{𝜀}}}$

$$

$={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }(A^{\prime }\cdot S))+B^{\prime }modq$

$={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }\cdot (A^{\prime }\cdot S+B^{\prime }))modq$

$={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }\cdot (p^{𝜀-1}M+E^{\prime }+K{p}^{𝜀}))modq$ # $K$ is some integer polynomials to represent the coefficient values that wrap around $p^{𝜀}$

$$

Let’s see how we derived the above relation. Suppose we compute $A^{\prime }\cdot S+B^{\prime }mod{p}^{𝜀}$, whose output will be $p^{𝜀-1}M+E^{\prime }$. Now, instead of using the plaintext secret key $S$, we use an encrypted secret key ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }S)$, where $S$ is a plaintext modulo $p^{𝜀}$, its scaling factor ${\mathrm{\Delta }}^{\prime }=\lfloor {\displaystyle \frac{q}{p^{𝜀}}}\rfloor$, and the ciphertext encrypting $S$ is in modulo $q$. Then, the result of homomorphically computing $A^{\prime }\cdot {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }S)+B^{\prime }$ will be an encryption of $p^{𝜀-1}M+E^{\prime }+K{p}^{𝜀}$, where $K{p}^{𝜀}$ stands for the wrapping-around coefficient values of the multiples of $p^{𝜀}$.

Notice that we did not reduce $K{p}^{𝜀}$ by modulo $p^{𝜀}$ during homomorphic decryption (without modulo-$q$ reduction), because such a homomorphic modulo reduction is not directly doable. Instead, we will handle $K{p}^{𝜀}$ in the later digit extraction step.

For simplicity, we will denote $Z=p^{𝜀-1}M+E^{\prime }mod{p}^{𝜀}$.

$$

3.

CoeffToSlot: Move the (encrypted) polynomial $Z$’s coefficients $z_0,z_i,\cdots ,z_{n-1}$ to the input vector slots of an RLWE ciphertext. This is done by computing:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(Z)\cdot n^{-1}\cdot \tilde{W}\cdot I_R^n$

, where $n^{-1}\cdot \tilde{W}\cdot I_R^n$ is the batch encoding matrix that converts input vector slot values into polynomial coefficients (Summary D-2.9.3 in §D-2.9.3).

$$

4.

Digit Extraction: We design a polynomial $G_{𝜀}(x)$ (a digit extraction polynomial) zeros out the least significant base-$p$ digit(s) by recursively evaluating the polynomial. Using each $z_i$ (i.e., the $i$-th coefficient of $Z$) as an input, we recursively evaluate $G_{𝜀}(z_i)$ total $𝜀-1$ times consecutively, which effectively zeros out the least significant $𝜀-1$ digits of the base-$p$ representation of $z_i$ (i.e., noise value), and keeps only the most significant base-$p$ digit of $x$ (i.e., plaintext value). Throughout the digit extraction, the value stored at the input vector slots of the ciphertext gets updated from $p^{𝜀-1}M+E^{\prime }+K{p}^{𝜀}$ to $p^{𝜀-1}M+K^{\prime }{p}^{𝜀}$.

$$

5.

SlotToCoeff: Homomorphically move each input vector slot’s value back to the (encrypted) polynomial coefficient position. This is done by homomorphically multiplying the decoding matrix ${\tilde{W}}^{\ast }$ to the ciphertext (Summary D-2.9.3 in §D-2.9.3).

$$

6.

Scaling Factor Re-interpretation: At this point, we have the ciphertext ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }\cdot (p^{𝜀-1}M+K^{\prime }{p}^{𝜀}))modq$, where the plaintext modulus is $p^{𝜀}$ and the plaintext scaling factor ${\mathrm{\Delta }}^{\prime }={\displaystyle \frac{q}{p^{𝜀}}}$. Without doing any actual additional computation, we can view this ciphertext as ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\displaystyle \frac{q}{p}}M))=modq$, which is an encryption of plaintext modulus $p$ whose scaling factor ${\mathrm{\Delta }}^{\prime }={\displaystyle \frac{q}{p}}$. This is because:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }\cdot (p^{𝜀-1}M+K^{\prime }{p}^{𝜀}))={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\displaystyle \frac{q}{p^{𝜀}}}\cdot (p^{𝜀-1}M+K^{\prime }{p}^{𝜀}))$

$={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }\left({\displaystyle \frac{q}{p}}M+K^{\prime }q\right)$

$={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }\left({\displaystyle \frac{q}{p}}M\right)$

In other words, we can view the ciphertext ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }\cdot (p^{𝜀-1}M+K^{\prime }{p}^{𝜀}))modq$ whose plaintext modulus is $p^{𝜀}$ and scaling factor ${\mathrm{\Delta }}^{\prime }={\displaystyle \frac{q}{p^{𝜀}}}$ as another ciphertext ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }M)modq$ whose plaintext modulus is $p$ and scaling factor $\mathrm{\Delta }={\displaystyle \frac{q}{p}}$.

Notice that the final ciphertext ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }\cdot M)$’s scaling factor stays the same as before the bootstrapping, while the original noises $E$ and $E^{\prime }$ have been eliminated. On the other hand, the homomorphic operation of CoeffToSlot, digit extraction, and SlotToCoeff must have accumulated additional noises, but their size is fixed and smaller than $E$ and $E^{\prime }$.

Next, we will explain each step more in detail.

D-2.11.2 Modulus Switch

The first step of the BFV bootstrapping is to do a modulus switch from $q$ to some prime power modulus $p^{𝜀}$ where $p^{𝜀}\ll q$. Before the bootstrapping, suppose the encrypted plaintext with noise is $\mathrm{\Delta }M+Emodq$. Then, after the modulus switch from $q\to p^{𝜀}$, the plaintext would scale down to $p^{𝜀-1}M+E^{\prime }mod{p}^{𝜀}$, where $E^{\prime }$ roughly contains $\lceil {\displaystyle \frac{p^{𝜀}}{q}}E\rfloor$ plus the modulus switching noise of the plaintext’s scaling factor $\mathrm{\Delta }\to p^{𝜀-1}$. The goal of the BFV bootstrapping is to zero out this noise $E^{\prime }$.

D-2.11.3 Homomorphic Decryption

Let’s denote the modulus-switched noisy plaintext as $Z=p^{𝜀-1}M+E^{\prime }mod{p}^{𝜀}$. We further denote polynomial $Z$’s each degree term’s coefficient $z_i$ as base-$p$ number as follows:

$z_i=z_{i,𝜀-1}{p}^{𝜀-1}+z_{i,𝜀-2}{p}^{𝜀-2}+\cdots +z_{i,1}p+z_{i,0}mod{p}^{𝜀}$

Then, $z_{i}mod{p}^{𝜀}$ is a base-$p$ number comprising $𝜀$ digits: $\{z_{i,𝜀-1},z_{i,𝜀-2},\cdots ,z_{i,0}\}$

We assume that the highest base-$p$ digit index for the noise is $𝜀-2$, which is equivalent to the noise budget, and the pure plaintext portion solely resides at the base-$p$ digit index $𝜀-1$ (i.e., the most significant base-$p$ digit in modulo $p^{𝜀}$). Given this assumption, we extract the noise-free plaintext by computing the following:

$\lceil {\displaystyle \frac{z_i}{p^{𝜀-1}}}\rfloor modp=z_{i,𝜀-1}$ # where the noise is assumed to be smaller than ${\displaystyle \frac{p^{𝜀-1}}{2}}$

The above formula is equivalent to shifting the base-$p$ number $z_i$ by $𝜀-1$ digits to the right (and rounding the decimal value). However, remember that we don’t have direct access to polynomial $Z=p^{𝜀-1}M+E^{\prime }mod{p}^{𝜀}$ unless we have the secret key $S$ to decrypt the ciphertext storing the plaintext. Instead, we can only derive $Z$ as an encrypted form. Specifically, we can homomorphically decrypt the modulus-switched ciphertext $(A^{\prime },B^{\prime })$ by using the encrypted secret key ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }S)$ as a bootstrapping key. For this ciphertext ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }S)$, the plaintext modulus is $p^{𝜀}$, the plaintext scaling factor is ${\mathrm{\Delta }}^{\prime }={\displaystyle \frac{q}{p^{𝜀}}}$, and the ciphertext modulus is $q$. With this encrypted secret key $S$, we homomorphically decrypt the encrypted $Z$ as follows:

$\left(\lceil {\displaystyle \frac{p^{𝜀}}{q}}\cdot A\rfloor ,\lceil {\displaystyle \frac{p^{𝜀}}{q}}\cdot B\rfloor \right)=(A^{\prime },B^{\prime })mod{p}^{𝜀}$

$A^{\prime }\cdot {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }S)+B^{\prime }modq$

$={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }(A^{\prime }\cdot S))+B^{\prime }modq$

$={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }\cdot (A^{\prime }\cdot S+B^{\prime }))modq$

$={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }\cdot (p^{𝜀-1}M+E^{\prime }+K{p}^{𝜀}))modq$ # $K$ is some integer polynomials to represent the coefficient values that wrap around modulo $p^{𝜀}$ as multiples of $p^{𝜀}$

$={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }Z)modq$

During this homomorphic decryption, we did not reduce the plaintext result by modulo $p^{𝜀}$, because the homomorphic decryption is a ciphertext-to-plaintext multiplication and addition done in the ciphertext modulus $q$ (not $p^{𝜀}$) by using $A^{\prime }$ and $B^{\prime }$ as plaintexts (with the plaintext modulus $p^e$) and ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }S)$ as a ciphertext (with the ciphertext modulus $q$). This is why the wrapping term $K{p}^{𝜀}$ is preserved in the plaintext after the homomorphic decryption– we will handle this term at the later stage of bootstrapping. Also, notice that the computation of $A^{\prime }\cdot {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }S)$ would not generate much noise. This is because $A^{\prime }$ is a plaintext modulo $p^{𝜀}$, and thus the new noise generated by ciphertext-to-plaintext multiplication is $A^{\prime }\cdot E_s$ (where $E_s$ is the encryption noise of ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }S)$). Since the ciphertext modulus $q\gg p^{𝜀}$, $q\gg A^{\prime }\cdot E_s$.

Once we have derived ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }Z)$, our next step is to remove the noise in the lower $𝜀-1$ digits (in terms of base-$p$ representation) of each $z_i$ for $0\le i\le n-1$. This is equivalent to transforming noisy ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }Z)={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }\cdot (p^{𝜀-1}M+E^{\prime }+K{p}^{𝜀}))$ into noise-free ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }M))$ where $\mathrm{\Delta }={\displaystyle \frac{q}{p}}$. BFV’s solution to do this is to design a $p$-degree polynomial function which computes the same logical result as $\lceil {\displaystyle \frac{z_i}{p^{𝜀-1}}}\rfloor modp$. We will later explain how to design this polynomial by using the digit extraction polynomial $G_{𝜀}(x)$ (§D-2.11.5).

However, in order to homomorphically evaluate this polynomial at each coefficient $z_i$ given the ciphertext ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }Z)$, we need to move polynomial $Z$’s each coefficient $z_i$ to the input vector slots of an RLWE ciphertext. This is because BFV supports homomorphic batched $\text{(+,⋅)}$ operations based on input vector slots of ciphertexts as operands. Therefore, we need to evaluate the noise-removing polynomial $G_{𝜀}(x)$ based on the values stored in the input vector slots of a ciphertext.

In the next sub-section, we will explain the CoeffToSlot procedure, a process of moving polynomial coefficients into input vector slots of a ciphertext homomorphically.

D-2.11.4 CoeffToSlot and SlotToCoeff

The goal of the CoeffToSlot step is to homomorphically move polynomial $Z$’s coefficients $z_i$ to input vector slots.

In Summary D-2.9.3 (in §D-2.9.3), we learned that the encoding formula for converting a vector of input slots $\overrightarrow{v}$ into a vector of polynomial coefficients $\overrightarrow{m}$ is: $\overrightarrow{m}=n^{-1}\cdot \tilde{W}\cdot I_n^R\cdot \overrightarrow{v}$, where $\tilde{W}$ is a basis of the $n$-dimensional vector space crafted as follows:

$\tilde{W}=\left[\begin{array}{cccccccc}\hfill 1\hfill & \hfill 1\hfill & \hfill \cdots \hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill \cdots \hfill & \hfill 1\hfill \\ \hfill ({\omega }^{J(\frac{n}{2}-1)})\hfill & \hfill ({\omega }^{J(\frac{n}{2}-2)})\hfill & \hfill \cdots \hfill & \hfill ({\omega }^{J(0)})\hfill & \hfill ({\omega }^{J_{\ast }(\frac{n}{2}-1)})\hfill & \hfill ({\omega }^{J_{\ast }(\frac{n}{2}-2)})\hfill & \hfill \cdots \hfill & \hfill ({\omega }^{J_{\ast }(0)})\hfill \\ \hfill {({\omega }^{J(\frac{n}{2}-1)})}^2\hfill & \hfill {({\omega }^{J(\frac{n}{2}-2)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(0)})}^2\hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-1)})}^2\hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-2)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J_{\ast }(0)})}^2\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill {({\omega }^{J(\frac{n}{2}-1)})}^{n-1}\hfill & \hfill {({\omega }^{J(\frac{n}{2}-2)})}^{n-1}\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(0)})}^{n-1}\hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-1)})}^{n-1}\hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-2)})}^{n-1}\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J_{\ast }(0)})}^{n-1}\hfill \end{array}\right]$

# where the rotation helper function $J(h)=5^{h}mod2n$

Therefore, given the input ciphertext $\mathsf{\text{𝖼𝗍}}={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }Z)modq$, we can understand its input vector slots as storing some values such that multiplying $n^{-1}\cdot \tilde{W}\cdot I_n^R$ to each of them turns them into a coefficient $z_i$ of polynomial $Z$. This implies that if we homomorphically multiply $n^{-1}\cdot \tilde{W}\cdot I_n^R$ to the input vector slots of ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }Z)$, then the resulting ciphertext’s $n$-dimensional input vector slots will contain the $n$ coefficients of $Z$, which is equivalent to moving the coefficients of $Z$ to the input vector slots. Therefore, the CoeffToSlot step is equivalent to homomorphically computing $n^{-1}\cdot \tilde{W}\cdot I_n^R\cdot {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^{\prime }Z)$. We can homomorphically compute matrix-vector multiplication by using the technique explained in §D-2.10.

After the CoeffToSlot step, we can homomorphically eliminate the noise in the lower $𝜀-1$ base-$p$ digits of each $z_i$ by homomorphically evaluating the noise-removing polynomial (to be explained in the next subsection).

After we get noise-free coefficients of $Z$, we need to move them back from the input vector slots to their original coefficient positions. This step is called SlotToCoeff, which is an exact inverse procedure of CoeffToSlot. We also learned in Summary D-2.9.3 (in §D-2.9.3) that the inverse matrix of $n^{-1}\cdot \tilde{W}\cdot I_n^R$ is ${\tilde{W}}^{\ast }$, where:

${\tilde{W}}^{\ast }=\left[\begin{array}{ccccc}\hfill 1\hfill & \hfill ({\omega }^{J(0)})\hfill & \hfill {({\omega }^{J(0)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(0)})}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J(1)})\hfill & \hfill {({\omega }^{J(1)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(1)})}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J(2)})\hfill & \hfill {({\omega }^{J(2)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(2)})}^{n-1}\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J(\frac{n}{2}-1)})\hfill & \hfill {({\omega }^{J(\frac{n}{2}-1)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(\frac{n}{2}-1)})}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J_{\ast }(0)})\hfill & \hfill {({\omega }^{J_{\ast }(0)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J_{\ast }(0)})}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J_{\ast }(1)})\hfill & \hfill {({\omega }^{J_{\ast }(1)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J_{\ast }(1)})}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J_{\ast }(2)})\hfill & \hfill {({\omega }^{J_{\ast }(2)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J_{\ast }(2)})}^{n-1}\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J_{\ast }(\frac{n}{2}-1)})\hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-1)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-1)})}^{n-1}\hfill \end{array}\right]$

Therefore, the SlotToCoeff step is equivalent to homomorphically multiplying ${\tilde{W}}^{\ast }$ to the output of the noise-eliminating polynomial evaluation.

In the next subsection, we will learn how to design the core algorithm of BFV, the noise elimination polynomial, based on the digit extraction polynomial $G_{𝜀}(x)$.

D-2.11.5 Digit Extraction

Remember we defined polynomial $Z$ as the scaled noisy plaintext: $Z=p^{𝜀-1}M+E^{\prime }+K{p}^{𝜀}=p^{𝜀-1}M+E^{\prime }mod{p}^{𝜀}$, and each $z_i$ is the $i$-th coefficient of $Z$ (where $0\le i\le n-1$). The goal of the digit extraction step is to homomorphically zero out the lower (base-$p$) $𝜀-1$ digits of each $z_i$, where the noise resides.

First, we always think of $z_i$ as a base-$p$ number (since this is a modulo-$p^{𝜀}$ value) as follows:

$z_i=z_{i,𝜀-1}{p}^{𝜀-1}+z_{i,𝜀-2}{p}^{𝜀-2}+\cdots +z_{i,2}{p}^2+z_{i,1}p+z_{i,0}mod{p}^{𝜀}$

Next, we define a new notation that denotes $z_i$ in a different way as follows:

$z_i=d_0+\left(\underset{j={𝜀}^{\prime }}{\overset{𝜀-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{d}_{\ast }{p}^j\right)$

, where $d_0\in {\mathbb{Z}}_p$, and $d_{\ast }\in 𝕀$, and ${𝜀}^{\prime }$ is $z_i$’s least significant base-$p$ digit index whose value is non-zero after digit index 0. Therefore, each $z_i\in {\mathbb{Z}}_{p^{𝜀}}$ is mapped to a unique set of $(d_0,d_{\ast },{𝜀}^{\prime })$.

Next, we define a lifting polynomial $F_{{𝜀}^{\prime }}$ in terms of $z_i$ and its associated $(d_0,d_{\ast },{𝜀}^{\prime })$ as follows:

$F_{{𝜀}^{\prime }}(z_i)\equiv d_{0}mod{p}^{{𝜀}^{\prime }+1}$

Verbally speaking, $F_{{𝜀}^{\prime }}(z_i)$ processes $z_i$ in such a way that it keeps $z_{i,0}$ (i.e., $z_i$’s value at the base-$p$ digit index 0) the same as before, then finds the next least significant base-$p$ digit whose value is non-zero (whose digit index is denoted as ${𝜀}^{\prime }$) and zeros it, during which the subsequent higher significant base-$p$ digits may get updated to any arbitrary values (i.e., the function doesn’t care about those values whose base-$p$ digit index is higher than ${𝜀}^{\prime }$ because they fall outside the modulo $p^{{𝜀}^{\prime }+1}$ range).

We will show an example of how $z_i$ is updated if it is evaluated by the $F_{{𝜀}^{\prime }}$ function recursively total $𝜀-1$ times in a row as follows:

$\underset{𝜀-1\text{ times}}{\underbrace{F_{𝜀-1}\cdots F_3\circ F_2\circ F_1}}(z_i)$

1st Recursion: $F_1(z_i)=c_{i,𝜀-1}{p}^{𝜀-1}+c_{i,𝜀-2}{p}^{𝜀-2}+\cdots +c_{i,2}{p}^2+0p+z_{i,0}mod{p}^{𝜀}$ # $F_1(z_i)\equiv z_{i,0}mod{p}^2$

2nd Recursion: $F_2\circ F_1(z_i)=c_{i,𝜀-1}^{\prime }{p}^{𝜀-1}+c_{i,𝜀-2}^{\prime }{p}^{𝜀-2}+\cdots +0p^2+0p+z_{i,0}mod{p}^{𝜀}$ # $F_1\circ F_2(z_i)\equiv z_{i,0}mod{p}^3$

3rd Recursion: $F_3\circ F_2\circ F_1(z_i)=c_{i,𝜀-1}^{″}{p}^{𝜀-1}+c_{i,𝜀-2}^{″}{p}^{𝜀-2}+\cdots +0p^3+0p^2+0p+z_{i,0}mod{p}^{𝜀}$ # $F_3\circ F_2\circ F_1(z_i)\equiv z_{i,0}mod{p}^4$

$⋮$

$(𝜀-1)$-th Recursion: $\underset{𝜀-1\text{ times}}{\underbrace{F_{𝜀-1}\circ \cdots \circ F_3\circ F_2\circ F_1}}(z_i)=0p^{𝜀-1}+0p^{𝜀-2}+\cdots +0p^2+0p+z_{i,0}mod{p}^{𝜀}$ # $F_{𝜀-1}\cdots F_3\circ F_2\circ F_1(z_i)\equiv z_{i,0}mod{p}^{𝜀}$

In the above recursive computation, notice that the order of using function $F_{{𝜀}^{\prime }}$ is specifically $F_1\to F_2\to F_3\to \cdots \to F_{𝜀-1}$. We choose this specific order because we assume that for the initial input $z_i$, we don’t know its associated ${𝜀}^{\prime }$ value (i.e., the least significant base-$p$ digit index whose value is non-zero after digit index 0). If we choose the order $F_1\to F_2\to F_3\to \cdots \to F_{𝜀-1}$, then regardless of the value of $z_i$, we get the universal guarantee that the final output will be $z_{i,0}mod{p}^{𝜀}$ (i.e., the value of the base-$p$ digit index 0).

Now, we define the digit extraction function $G_{𝜀,v}(z_i)$ as follows:

$G_{𝜀,v}(z_i)=z_i-(\underset{v\text{ times}}{\underbrace{F_{𝜀-1}\circ F_{𝜀-2}\circ F_{𝜀-3}\cdots \circ F_{𝜀-v}}}(z_i)mod{p}^{𝜀}$

Notice that $G_{𝜀,v}(z_i)$ is equivalent to zeroing out the least significant base-$p$ digit of $z_i$. Let’s see what happens if we recursively evaluate $G_{𝜀,v}$ at $z_i$ for $v=𝜀-1,𝜀-2,\cdots ,1$ (total $𝜀-1$ times):

1st Recursion: $G_{𝜀,𝜀-1}(z_i)=z_{i,𝜀-1}{p}^{𝜀-1}+z_{i,𝜀-2}{p}^{𝜀-2}+\cdots +z_{i,2}{p}^2+z_{i,1}p+0mod{p}^{𝜀}$

2nd Recursion: $G_{𝜀,𝜀-2}\circ G_{𝜀,𝜀-1}(z_i)=z_{i,𝜀-1}{p}^{𝜀-1}+z_{i,𝜀-2}{p}^{𝜀-2}+\cdots +z_{i,2}{p}^2+0p+0mod{p}^{𝜀}$

3rd Recursion: $G_{𝜀,𝜀-3}\circ G_{𝜀,𝜀-2}\circ G_{𝜀,𝜀-1}(z_i)=z_{i,𝜀-1}{p}^{𝜀-1}+z_{i,𝜀-2}{p}^{𝜀-2}+\cdots +0p^2+0p+0mod{p}^{𝜀}$

$⋮$

$𝜀-1$-th Recursion: $G_{𝜀,1}\circ \cdots \circ G_{𝜀,𝜀-2}\circ G_{𝜀,𝜀-1}(z_i)=z_{i,𝜀-1}{p}^{𝜀-1}+0p^{𝜀-2}+\cdots +0p+0mod{p}^{𝜀}$

As shown above, recursively evaluating $G_{𝜀,v}$ at $z_i$ for $v=𝜀-1,𝜀-2,\cdots ,1$ (total $𝜀-1$ times) is equivalent to zeroing out the least significant (base-$p$) $𝜀-1$ digits modulo $p^{𝜀}$.

By recursively applying the digit extraction function $G_{𝜀,v}$ as above, we can zero out the noise stored at the least significant (base-$p$) $𝜀-1$ digit indices.

Now, our final remaining task is to design the actual lifting polynomial $F_{{𝜀}^{\prime }}(z_i)$ that implements $G_{𝜀,v}$.

Designing $F_{{𝜀}^{\prime }}(z_i)$: We will derive $F_{{𝜀}^{\prime }}(z_i)$ based on the following steps.

1.

Let’s define $z_i=z_{i,0}+\underset{j={𝜀}^{\prime }}{\overset{𝜀-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{z}_{i,j}{p}^j$ = $z_{i,0}+k{p}^{{𝜀}^{\prime }}$

$$

, where $z_{i,0}\in [0,p-1]$, ${𝜀}^{\prime }$ is the least significant base-$p$ digit’s index of $z_i$ which has a non-zero value, and $k=p^{-{𝜀}^{\prime }}\cdot \underset{j={𝜀}^{\prime }}{\overset{𝜀-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{z}_{i,j}{p}^j\in [0,p^{𝜀-{𝜀}^{\prime }}-1]$.

Basically, $z_i$ can be any number in ${\mathbb{Z}}_{p^{𝜀}}$ whose base-$p$ representation has 0s between the base-$p$ digit index greater than 0 and smaller than ${𝜀}^{\prime }$.

$$

2.

Claim: $z_i^p\equiv z_{i,0}modp$

Proof. Fermat’s Little Theorem states $a^{p-1}\equiv 1modp$ for all $a\in {\mathbb{Z}}_p$ and prime $p$. Therefore, $z_i\equiv z_{i,0}^{p}modp$. □

3.

Claim: $z_i^p\equiv z_{i,0}^{p}mod{p}^{{𝜀}^{\prime }+1}$

Proof. $$

$${(z_{i,0}+k{p}^{{𝜀}^{\prime }})}^{p}mod{p}^{{𝜀}^{\prime }+1}=\text{∑}_{j=0}^p\left(\genfrac{}{}{0.0pt}{}{p}{j}\right)\cdot z_{i,0}^j\cdot {(k{p}^{{𝜀}^{\prime }})}^{p-j}mod{p}^{{𝜀}^{\prime }+1}\text{\# binomial expansion formula}$$

$=z_{i,0}^p$ □

$$

4.

Claim: Given $p$ and ${𝜀}^{\prime }$ are fixed, there exists ${𝜀}^{\prime }+1$ polynomials $f_0,f_1,f_2,\cdots ,f_{{𝜀}^{\prime }}$ (where each polynomial is at most $p-1$ degrees) such that any $z_i$ (i.e., any number whose base-$p$ representation has 0s between the base-$p$ digit index greater than 0 and smaller than ${𝜀}^{\prime }$) can be expressed as the following formula:

$z_i^p\equiv \underset{j=0}{\overset{{𝜀}^{\prime }}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{f}_j(z_{i,0})\cdot p^{j}mod{p}^{{𝜀}^{\prime }+1}$

Proof. $$

$z_i^{p}mod{p}^{{𝜀}^{\prime }+1}$ can be expressed as a base-$p$ number as follows:

$z_i^{p}mod{p}^{{𝜀}^{\prime }+1}=c_0+c_{1}p+c_2{p}^2+\cdots +c_{{𝜀}^{\prime }}{p}^{{𝜀}^{\prime }}$

$$

Based on step 3’s claim ($z_i^p\equiv z_{i,0}^{p}mod{p}^{{𝜀}^{\prime }+1}$), we know that the value of $z_i^{p}mod{p}^{{𝜀}^{\prime }+1}$ depends only on $z_{i,0}$ (given $p$ and ${𝜀}^{\prime }$ are fixed). Therefore, we can imagine that there exists some function $f(z_{i,0})$ whose input is $z_{i,0}\in [0,p-1]$ and the output is $z_i^p\in [0,p^{{𝜀}^{\prime }+1}-1]$. Alternatively, we can imagine that there exist ${𝜀}^{\prime }+1$ different functions $f_0,f_1,\cdots ,f_{{𝜀}^{\prime }}$ such that each $f_j$ is a polynomial whose input is $z_{i,0}\in [0,p-1]$ and the output is $c_i\in [0,p-1]$, and $z_i^p\equiv \underset{j=0}{\overset{{𝜀}^{\prime }}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{f}_j(z_{i,0})\cdot p^{j}mod{p}^{{𝜀}^{\prime }+1}$. The input and output domain of each polynomial $f_j$ is $[0,p-1]$. Therefore, we can design each $f_j$ as a $(p-1)$-degree polynomial and derive each $f_j$ based on polynomial interpolation (§A-15) by using $(p-1)$ coordinate values.

Note that whenever we increase ${𝜀}^{\prime }$ to ${𝜀}^{\prime }+1$, we add a new polynomial $f_{{𝜀}^{\prime }+1}$. However, the previous polynomials $f_0,f_1,\cdots ,f_{{𝜀}^{\prime }}$ stay the same as before, because increasing ${𝜀}^{\prime }$ by 1 only adds a new base-$p$ constant $c_{{𝜀}^{\prime }+1}$ for the highest base-$p$ digit, while keeping the lower-digit constants $c_0,c_1,\cdots ,c_{{𝜀}^{\prime }}$ the same as before. Therefore, the polynomials $f_0,f_1,\cdots ,f_{{𝜀}^{\prime }}$, each of which computes $c_0,c_1,\cdots ,c_{{𝜀}^{\prime }}$, also stay the same as before. □

5.

Claim: The formula in step 4’s claim can be further concretized as follows:

$z_i^p\equiv z_{i,0}+\underset{j=1}{\overset{{𝜀}^{\prime }}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{f}_j(z_{i,0})\cdot p^{j}mod{p}^{{𝜀}^{\prime }+1}$

Proof. $$

According to step 2’s claim ($z_i^p\equiv z_{i,0}modp$), we know that the following base-$p$ representation of $z_i^p$:

$z_i^{p}mod{p}^{{𝜀}^{\prime }+1}=c_0+c_{1}p+c_2{p}^2+\cdots +c_{𝜀-1}{p}^{{𝜀}^{\prime }}$

$$

will be the following:

$z_i^{p}mod{p}^{{𝜀}^{\prime }+1}=z_{i,0}+c_{1}p+c_2{p}^2+\cdots +c_{𝜀-1}{p}^{{𝜀}^{\prime }}$

$$

, since the least significant base-$p$ digit of $z_i^p$ in the base-$p$ representation is always $z_{i,0}$. Thus, the formula in step 4’s claim:

$z_i^p=\underset{j=0}{\overset{{𝜀}^{\prime }}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{f}_j(z_{i,0})\cdot p^{j}mod{p}^{{𝜀}^{\prime }+1}$

$$

can be further concretized as follows:

$$

$z_i^p=z_{i,0}+\underset{j=1}{\overset{{𝜀}^{\prime }}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{f}_j(z_{i,0})\cdot p^{j}mod{p}^{{𝜀}^{\prime }+1}$ □

6.

Claim: $z_i^p-\underset{j=1}{\overset{{𝜀}^{\prime }}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{f}_j(z_i)\cdot p^j\equiv z_{i,0}mod{p}^{{𝜀}^{\prime }+1}$

Proof. $$ Remember that in step 1, we defined $z_i$ as: $z_i=z_{i,0}+\underset{j={𝜀}^{\prime }}{\overset{𝜀-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{z}_{i,j}{p}^j$. Therefore, $z_{i}mod{p}^{{𝜀}^{\prime }}=z_{i,0}$. This implies that for each polynomial $f_j$, the following is true:

$f_j(z_{i,0})\equiv f_j(z_i)mod{p}^{{𝜀}^{\prime }}$

$$

We can further derive the following:

$f_j(z_{i,0})\cdot p^j\equiv f_j(z_i)\cdot p^{j}mod{p}^{{𝜀}^{\prime }+1}$ (where $i\ge 1$)

$$

The above is true because:

$f_j(z_{i,0})\equiv f_j(z_i)mod{p}^{{𝜀}^{\prime }}$

$f_j(z_{i,0})=f_j(z_i)+q\cdot p^{{𝜀}^{\prime }}$ (for some integer $q$)

$f_j(z_{i,0})\cdot p^j=f_j(z_i)\cdot p^j+q\cdot p^{{𝜀}^{\prime }}\cdot p^j$ # multiplying $p^j$ to both sides

$f_j(z_{i,0})\cdot p^j=f_j(z_i)\cdot p^j+q\cdot p^{j-1}\cdot p^{{𝜀}^{\prime }+1}$ # $f_j(z_{i,0})\cdot p^j$ and $f_j(z_i)\cdot p^j$ differ by some multiple of $p^{{𝜀}^{\prime }+1}$

$$

Therefore, $f_j(z_{i,0})\cdot p^j\equiv f_j(z_i)\cdot p^{j}mod{p}^{{𝜀}^{\prime }+1}$.

$$

Now, given step 5’s claim ($z_i^p\equiv z_{i,0}+\underset{j=1}{\overset{{𝜀}^{\prime }}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{f}_j(z_i)\cdot p^{j}mod{p}^{{𝜀}^{\prime }+1}$), we can derive the following:

$z_i^p-\underset{j=1}{\overset{{𝜀}^{\prime }}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{f}_j(z_i)\cdot p^{j}mod{p}^{{𝜀}^{\prime }+1}$

$\equiv (z_{i,0}+\underset{j=1}{\overset{{𝜀}^{\prime }}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{f}_j(z_{i,0})\cdot p^j)-\sum _{j=1}^{{𝜀}^{\prime }}{f}_j(z_i)\cdot p^{j}mod{p}^{{𝜀}^{\prime }+1}$ # applying step 5’s claim

$\equiv (z_{i,0}+\underset{j=1}{\overset{{𝜀}^{\prime }}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{f}_j(z_i)\cdot p^j)-\sum _{j=1}^{{𝜀}^{\prime }}{f}_j(z_i)\cdot p^{j}mod{p}^{{𝜀}^{\prime }+1}$ # since $f_j(z_{i,0})\cdot p^j=f_j(z_i)\cdot p^{j}mod{p}^{{𝜀}^{\prime }+1}$

$\equiv z_{i,0}mod{p}^{{𝜀}^{\prime }+1}$ □

7.

Finally, we define the lifting polynomial $F_{{𝜀}^{\prime }}(z_i)$ as follows:

$F_{{𝜀}^{\prime }}(z_i)=z_i^p-\underset{j=1}{\overset{{𝜀}^{\prime }}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{f}_j(z_i)\cdot p^j$

$F_{{𝜀}^{\prime }}(z_i)\equiv z_{i,0}mod{p}^{{𝜀}^{\prime }+1}$

The above relation implies that $F_{{𝜀}^{\prime }}(x)mod{p}^{{𝜀}^{\prime }+1}$ is equivalent to the least significant base-$p$ digit of $x$ (according to step 6’s claim). Therefore, if we plug in $z_i$ into $F_{{𝜀}^{\prime }}(x)$ and regard ${𝜀}^{\prime }=1$, then the output is some number whose least significant base-$p$ digit is $z_{i,0}mod{p}^2$ and the 2nd least significant base-$p$ digit is $0mod{p}^2$. As we recursively apply the output back to $F_{{𝜀}^{\prime }}(x)$ and increment ${𝜀}^{\prime }$ by 1, we iteratively zero out the 2nd least significant base-$p$ digit, the 3rd least significant base-$p$ digit, and so on. We repeat this process for $𝜀-1$ times to zero out the upper $𝜀-1$ base-$p$ digits, keeping only the least significant digit as it is (i.e., $z_{i,0}$). Therefore, $F_{{𝜀}^{\prime }}(x)$ is a valid lifting polynomial that can be iteratively used to extract the least significant digit of $z_{i}mod{p}^{𝜀}$.