A question about digit extraction of BFV/BGV's bootstrapping

FHE Questions
1

Hi,

I am reading this paper to learn how BFV’s (and BGV’s) bootstrapping works. But I don’t understand how the digit extraction works. In the paper’s section:

5.3 Digit-Extraction for Plaintext Space Modulo p^r

The key algorithm of digit extraction is as follows:

![image|690x55](upload://fmCMIMOVLHjoB9trSfBUcmtiRgp.png

image
image806×286 19 KB

However, I don’t follow the correctness of this algorithm. Specifically, I break down my question into 3.

Q1. In Line 5 of the above algorithm, is it correct that F_e(w_{j, k}) extracts the LSD (least significant digit) of base-p representation of w_{j, k}? If yes, then I suppose Line 5’s w_{j, k + 1} \leftarrow F_e(w_{j, k}) specifically means:
w_{j, k + 1} \leftarrow F_e(w_{j, k}) \bmod p

Is this correct?

Q2. If Q1 is yes, then I don’t understand how Line 5 works over iterations. For example, in the 1st outer for-loop iteration (k = 0), at Line 5 we store w_{0, 1} \leftarrow F_e(w_{0, 0}), which is the LSD of base-p representation of the initial input z. However, in the 2nd outer for-loop iteration (k = 1), at Line 5 we store w_{0, 2} \leftarrow F_e(w_{0, 1}), where F_e(w_{0, 1}) does not make sense if F_e(w_{0, 1}) returns the LSD of base-p representation of w_{0, 1} (which is the LSD of base-p representation of the initial input z).

Q3. Does Line 6 remove y's LSD in base-p representation and then shift the digit by 1 position to the right? In other words, if y was originally c_0 + c_1p + c_2p^2 + \cdots, then does Line 6 update y as c_1 + c_2p + c_3p^2 + \cdots?

Q4. I wonder why we have to use 2 for-loops instead of 1 for-loop. I think the following algorithm could work:

\text{INPUT: } (z, e)
\text{for } k = 0 \text{ to } e - 1:
\text{ } \text{ }\text{ } y \leftarrow F_e(z) \bmod p
\text{ } \text{ }\text{ } z \leftarrow \dfrac{z - y}{p}
\text{return } z

The above algorithm shifts the original input z by e digits to the right in base-p representation. Why can’t we use the above algorithm for BFV’s digit extraction? (In my above suggestion, I set e’ = 0, but I believe this still guarantees correctness of Lemma 5.3 in the paper because the binomial expansion’s correctness still holds even if e’ = 0, and therefore this also guarantees correctness of Lemma Corollary 5.4 and 5.5).

2

I found a solution for this question: https://arxiv.org/pdf/1906.02867

image
image967×490 54.5 KB

Actually, my understanding on the F_e(X) function was a bit wrong. I present my correct understanding below.

Suppose we have an input value z = z_0 + z_1p + z_2p^2 + \cdots + z_{e-1}p^{e-1}, which is a base-p representation of the input value z, and our goal is to extract the lowest digit z_0. First, we can re-write z as z = z_0 + z'p, where
e' = 1
z' = z_1 + z_2p + z_3p^2 + \cdots + z_{e-1}p^{e-2}.
Now, we evaluate F_e(z_0 + z'_1p) \equiv z_0 \bmod p^2.
This means that
F_e(z_0 + z'_1p) \bmod p^2 = z_0 + 0p + z^{\langle 1 \rangle}_2p^2 + z^{\langle 1 \rangle}_3p^3 + \cdots + z^{\langle 1 \rangle}_{e-1}p^{e-1} \bmod p^2
for some \{z^{\langle 1 \rangle}_2, z^{\langle 1 \rangle}_3, \cdots, z^{\langle 1 \rangle}_{e-1}\} that we don’t know (and we don’t need to know). Notice that applying F_e(X) once to z successfully removes the second-lowest digit of z in base-p representation.

In the 2nd round, we let
y_1 = F_e(z_0 + z'_1p) \bmod p^2
e' = 2
z' = z^{\langle 1 \rangle}_2 + z^{\langle 1 \rangle}_3p + z^{\langle 1 \rangle}_4p^2 + \cdots + z^{\langle 1 \rangle}_{e-1}p^{e-3}
Then, we compute:
F_e(y_1) \bmod p^3 = F_e(z_0 + z'p^2) \bmod p^3
= z_0 + 0p + 0p^2 + z^{\langle 1 \rangle}_3p^3 + \cdots + z^{\langle 1 \rangle}_{e-1}p^{e-1}
Notice that applying F_e(X) twice to z successfully removes the second-lowest and third-lowest digits of z in base-p representation.

We continue the above rounds for total e - 1 times. Then, we get:
F_e \circ \cdots \circ F_e \circ F_e \circ F_e (z) \equiv z_0 \bmod p^e
, which eliminates all higher digits of z except for the least significant digit’s value z_0 in base-p representation.

After extracting the least significant digit, we subtract it from the original value z and divide it by p, which effectively shifts z by 1 digit to the right while keeping all other upper-digit values the same as before. We do this right shifting for total r times, given the noise values are within the lowest r digits of z in base-p reprentation. Then, we eliminate all noise from z and extract only the noise-free plaintext value. Then, we can scale up the plaintext value again by the original scaling factor \Delta, and then do SlotToCoeff transition (i.e., apply decoding to it, homomorphically). Then, the noise-removed plaintext values will be placed in the coefficients of the plaintext polynomial as a scaled form: \Delta M. However, the new noise E generated during digit extraction and SlotToCoeff will be also added to it. Thus, we will have a form of \Delta M + E.