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 \mathbb{Z}$ 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^{𝜀}$, shifted to the right by 1 base-$p$ digit. Here, where the noise located at the least significant digits in a base-$p$ (prime) representation is zeroed out and shifted right. For example, $G_{𝜀}(3p^3+4p^2+6p+2)=3p^2+4p^1+6mod{p}^{𝜀}$. Given that the noise resides in the least significant $𝜀-1$ digits in base-$p$ representation, we can homomorphically and recursively evaluate $G_{𝜀}(x)$ total $𝜀-1$ times in a row, which zeroes out and removes 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 it is that the noise gets successfully zeroed out; however, the computation overhead becomes larger. If $𝜀$ is small, the computation gets faster, but the digit-wise distance between the noise and the plaintext decreases, potentially corrupting the plaintext during bootstrapping, because removing the most significant noise digit may also remove the least significant plaintext digit. 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{𝖱𝖫𝖶𝖤}}}_{{\mathrm{\Delta }}^{\prime }S,\sigma }(S)modq$, which is the secret key $S$ encrypted by $S$ (itself) modulo $q$ with the plaintext scaling factor ${\mathrm{\Delta }}^{\prime }$. 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)$ (i.e., a digit extraction polynomial) that zeros out the least significant base-$p$ digit(s) modulo $p^{𝜀}$. The digit extraction procedure recursively applies $G_2\circ G_3\circ \cdots \circ G_{𝜀-1}\circ G_{𝜀}(x)$ to the input $x$ to eliminate the least significant (base-$p$) $𝜀-2$ digits of input $x$ and shifts them to the right. Regarding the input $x$, we assume the noise resides in the least significant (base-$p$) $𝜀-2$ digits, and the message $m$ resides in the higher base-$p$ digits modulo $p^{𝜀}$. Therefore, digit extraction has the effect of zeroing out and deleting (i.e., shifting to the right) the least significant $𝜀-1$ digits of the base-$p$ representation of $p^{𝜀-1}m+e$. This digit extraction is performed homomorphically. Throughout the digit extraction, the scaled plaintext message with noise stored at the input vector slots of the ciphertext gets updated from $p^{𝜀-1}M+E^{\prime }+K{p}^{𝜀}$ to $M+K^{\prime }p$. During digit extraction, we also use a special method called scaling factor re-interpretation, which conceptually increases the scaling factor ${\mathrm{\Delta }}^{\prime }=\lfloor {\displaystyle \frac{q}{p^{𝜀}}}\rfloor$ over each round of digit extraction to $\lfloor {\displaystyle \frac{q}{p^{𝜀}-1}}\rfloor ,\lfloor {\displaystyle \frac{q}{p^{𝜀}-2}}\rfloor ,\dots ,\lfloor {\displaystyle \frac{q}{p}}\rfloor$, which equivalently has the conceptual effect of dividing the scaled message and noise stored in the plaintext slots by $p$ (i.e., shift to the right by 1 base-$p$ digit) as follows:

Input: $\lfloor {\displaystyle \frac{q}{p^{𝜀}}}\rfloor \cdot \left(p^{𝜀-1}M+E^{\prime }+K{p}^{𝜀}\right)$

Round 1: $\lfloor {\displaystyle \frac{q}{p^{𝜀-1}}}\rfloor \cdot \left(p^{𝜀-2}M+\lfloor {\displaystyle \frac{E^{\prime }}{p}}\rfloor +K{p}^{𝜀-1}\right)$

Round 2: $\lfloor {\displaystyle \frac{q}{p^{𝜀-2}}}\rfloor \cdot \left(p^{𝜀-3}M+\lfloor {\displaystyle \frac{E^{\prime }}{p^2}}\rfloor +K{p}^{𝜀-2}\right)$

$⋮$

Round $𝜀-1$: $\lfloor {\displaystyle \frac{q}{p}}\rfloor \cdot (M+\mathit{𝐾𝑝})$

$$

Importantly, the scaling factor re-interpretation does not require any actual computation; we only change the way of interpreting the ciphertext. We will cover this in more detail. later.

$$

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). The final output of this step is $={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }\left(\lfloor {\displaystyle \frac{q}{p}}\rfloor M+E^{⟨b⟩}\right)$, where $E^{⟨\text{b}⟩}$ is a new small noise term generated during the homomorphic operation of CoeffToSlot, digit extraction, and SlotToCoeff. The size of $E^{⟨\text{b}⟩}$ is fixed and smaller than $E$ and $E^{\prime }$.

Next, we will explain each step in more 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 (base-$p$) $𝜀-1$ 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 that we defined polynomial $Z$ as the scaled noisy plaintext: $Z=p^{𝜀-1}M+E^{\prime }+K{p}^{𝜀}\equiv 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 and delete (i.e., shift to the right) 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$ representation (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+d_{\ast }{p}^{{𝜀}^{\prime }}$

, where $d_0\in {\mathbb{Z}}_p$, and $d_{\ast }\in \mathbb{Z}$, 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 be updated to 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 a total of $𝜀-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 do not 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 obtain the universal guaranty 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_{𝜀}(z_i)={\lfloor {\displaystyle \frac{z_i}{p}}\rfloor }_p=(z_i-(\underset{𝜀-1\text{ times}}{\underbrace{F_{𝜀-1}\circ F_{𝜀-2}\circ F_{𝜀-3}\cdots \circ F_3\cdots \circ F_2\cdots \circ F_1}}(z_i))\cdot |p^{-1}{|}_q$

, where ${\lfloor \rfloor }_p$ denotes division by $p$ and rounding down to the nearest multiple of $p$. Verbally speaking, $G_{𝜀,v}(z_i)$ is equivalent to zeroing out the least significant base-$p$ digit of $z_i$ and then shifting to the right by 1 base-$p$ digit. The shifting is done by inverse $p$ multiplication (i.e., $|p^{-1}{|}_q$). Notice that the last base-$p$ digit of $z_i-(F_{𝜀-1}\circ F_{𝜀-2}\circ F_{𝜀-3}\cdots \circ F_1(z_i))$ is 0, which is exactly divisible by $p$. Thus, multiplying by the inverse $p$ has the effect of exact division (i.e., shifting the whole base-$p$ representation by 1 digit to the right). The reason why the inverse $p$ is in modulo $q$ is that we are currently under the BFV ciphertext relation: $\mathsf{\text{𝖢𝗈𝖾𝖿𝖿𝖳𝗈𝖲𝗅𝗈𝗍}}((A^{\prime },B^{\prime }))=(A^{⟨c\to s⟩},B^{⟨c\to s⟩})modq$, whose plaintext slots store the coefficients of ${\mathrm{\Delta }}^{\prime }\cdot (p^{𝜀-1}M+E^{\prime }+K^{⟨1⟩}{p}^{𝜀})modq$. Upon homomorphically computing $(z_i-(F_{𝜀-1}\circ F_{𝜀-2}\circ F_{𝜀-3}\cdots \circ F_3\cdots \circ F_2\cdots \circ F_1)$ as part of the 1st round of digit extraction, the ciphertext is updated to $(A^{⟨g_1⟩},B^{⟨g_1⟩})modq$, whose plaintext slots store the coefficients of ${\mathrm{\Delta }}^{\prime }\cdot (p^{𝜀-1}M+{\lfloor E^{\prime }\rfloor }_p+K^{⟨1⟩}{p}^{𝜀})modq$, where ${\lfloor E^{\prime }\rfloor }_p$ is equivalent to rounding $E^{\prime }$ down to the nearest multiple of $p$. At this point (i.e., just before inverse-$p$ multiplication in the first round), the ciphertext holds the following relation:

$A^{⟨g_1⟩}\cdot S+B^{⟨g_1⟩}={\mathrm{\Delta }}^{\prime }\cdot (p^{𝜀-1}M+{\lfloor E^{\prime }\rfloor }_p+K^{⟨1⟩}{p}^{𝜀})+E^{⟨g_1⟩}modq$

, where $E^{⟨g_1⟩}$ is the combined noise of the SlotToCoeff step and the first part of the 1st round of digit extraction. We could consider multiplying $|p^{-1}{|}_q$ to both sides of the relation to scale down $p^{𝜀-1}M,{\lfloor E^{\prime }\rfloor }_p,$ and $K^{⟨1⟩}{p}^{𝜀}$ by $p$. However, this causes a noise explosion problem, because this scaling will be also applied to the $E^{⟨g_1⟩}$ term, and $|p^{-1}{|}_q{E}^{⟨g_1⟩}$ is a huge value. To selectively apply the inverse-$p$ multiplication only to those terms of interest, we use the scaling factor re-interpretation technique.

Scaling Factor Re-interpretation: Although we previously explained that $G_{𝜀}$ involves the multiplication by $|p^{-1}{|}_q$, technically, we skip this multiplication and instead conceptually re-interpret the scaling factor ${\mathrm{\Delta }}^{\prime }$ as $\lfloor {\displaystyle \frac{q}{p^{𝜀}}}\rfloor \to \lfloor {\displaystyle \frac{q}{p^{𝜀}-1}}\rfloor \to \lfloor {\displaystyle \frac{q}{p^{𝜀}-2}}\rfloor \to \cdots ,\lfloor {\displaystyle \frac{q}{p}}\rfloor$ across $𝜀-1$ rounds of digit extraction. During this re-interpretation, each step’s $p$ being decreased in the denominator of the scaling factor is conceptually placed back into the bracket. Applying the re-interpretation of the scaling factor, the digit extraction procedure (without explicit multiplication by $|p^{-1}{|}_q$ at each round) is performed as follows:

Input: $\lfloor {\displaystyle \frac{q}{p^{𝜀}}}\rfloor \cdot (p^{𝜀-1}M+E^{\prime }+K{p}^{𝜀})modq$

1st Round: $G_{𝜀}(z_i)\underset{}{\overset{\text{effect}}{==\Rightarrow }}\lfloor {\displaystyle \frac{q}{p^{𝜀-1}}}\rfloor \cdot (p^{𝜀-2}M+\lfloor {\displaystyle \frac{E^{\prime }}{p}}\rfloor +K^{⟨1⟩}{p}^{𝜀-1})modq$

2nd Round: $G_{𝜀-1}\circ G_{𝜀}(z_i)\underset{}{\overset{\text{effect}}{==\Rightarrow }}\lfloor {\displaystyle \frac{q}{p^{𝜀-2}}}\rfloor \cdot (p^{𝜀-3}M+\lfloor {\displaystyle \frac{E^{\prime }}{p^2}}\rfloor +K^{⟨2⟩}{p}^{𝜀-2})modq$

3rd Round: $G_{𝜀-2}\circ G_{𝜀-1}\circ G_{𝜀}(z_i)\underset{}{\overset{\text{effect}}{==\Rightarrow }}\lfloor {\displaystyle \frac{q}{p^{𝜀-3}}}\rfloor \cdot (p^{𝜀-4}M+\lfloor {\displaystyle \frac{E^{\prime }}{p^3}}\rfloor +K^{⟨3⟩}{p}^{𝜀-3})modq$

$⋮$

$𝜀-1$-th Round: $G_2\circ \cdots \circ G_{𝜀}(z_i)\underset{}{\overset{\text{effect}}{==\Rightarrow }}\lfloor {\displaystyle \frac{q}{p}}\rfloor \cdot (M+K^{⟨𝜀-1⟩}p)modq$

Note that the scaling factor re-interpretation does not involve any actual computation, but only changes our way of interpreting the scaling factor. Notice that at the end of the final round, the plaintext scaling factor becomes $\lfloor {\displaystyle \frac{q}{p}}\rfloor$, which is the desired plaintext scaling factor for standard BFV ciphertexts. Therefore, the scaling factor re-interpretation has three benefits: (1) we skip explicit multiplication by $|p^{-1}{|}_q$ at each round; (2) we prevent noise explosion; (3) at the end of all rounds, the plaintext scaling factor becomes the desired value for standard BFV ciphertexts, gracefully completing the bootstrapping procedure.

Meanwhile, there are two important points to be aware of. First, each $i$-th round of scaling factor re-interpretation creates a small drift error in the scaling factor due to the difference ${𝜖}_i=p^{-1}\cdot \lfloor {\displaystyle \frac{q}{p^{𝜀-i}}}\rfloor -\lfloor {\displaystyle \frac{q}{p^{𝜀-i+1}}}\rfloor$, where $0\le {𝜖}_i<p$. Therefore, an additional drift error $E_i^{⟨\text{re}⟩}$ is created at each $i$-th round, which is small enough to be bounded by:

$E_i^{⟨\text{re}⟩}\le {𝜖}_i\cdot (p^{𝜀-i-1}M+\lfloor {\displaystyle \frac{E^{\prime }}{p^i}}\rfloor +K^{⟨i⟩}{p}^{𝜀-i})<p^{𝜀-1}M+\lfloor {\displaystyle \frac{E^{\prime }}{p}}\rfloor +K^{⟨i⟩}{p}^{𝜀+1}\ll \lfloor {\displaystyle \frac{q}{p^{𝜀}}}\rfloor$

Second, at each $i$-th round of digit extraction, the plaintext operands used for ciphertext-to-plaintext homomorphic operations should encode their values with the specific scaling factor interpreted at that round: ${\mathrm{\Delta }}_i^{\prime }=\lfloor {\displaystyle \frac{q}{p^{𝜀-i+1}}}\rfloor$.

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

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

1.

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

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

2.

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}=\underset{j=0}{\overset{p}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}\left(\genfrac{}{}{0.0pt}{}{p}{j}\right)\cdot z_{i,0}^j\cdot {(k{p}^{{𝜀}^{\prime }})}^{p-j}mod{p}^{{𝜀}^{\prime }+1}$ $▹$ binomial expansion formula

$\equiv z_{i,0}^{p}mod{p}^{{𝜀}^{\prime }+1}$ $▹$ all terms where $j<p$ are $0mod{p}^{{𝜀}^{\prime }+1}$ □

$$

3.

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}$. In this case, 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$ 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. □

4.

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\equiv c_0+c_{1}p+c_2{p}^2+\cdots +c_{{𝜀}^{\prime }}{p}^{{𝜀}^{\prime }}mod{p}^{{𝜀}^{\prime }+1}$

$$

will be the following:

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

$$

, since step 2’s claim implies that 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\equiv \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\equiv z_{i,0}+\underset{j=1}{\overset{{𝜀}^{\prime }}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{f}_j(z_{i,0})\cdot p^{j}mod{p}^{{𝜀}^{\prime }+1}$ □

5.

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 }}$

$$

Next, we derive the following:

$f_j(z_{i,0})\cdot p^j\equiv f_j(z_i)\cdot p^{j}mod{p}^{{𝜀}^{\prime }+1}$ (where $j\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,0})\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}$ $▹$ applying $f_j(z_{i,0})\cdot p^j\equiv f_j(z_i)\cdot p^{j}mod{p}^{{𝜀}^{\prime }+1}$

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

6.

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}^{𝜀}$.