However, the boostrapping method based on digit extraction seems to only reset the noise. In fact, noise resetting can be also done by modulus switching after cipher-cipher multiplication. From my understanding, the purpose of rescaling after each cipher-cipher multiplication is to reduce the squared scaling factor \Delta^2 to \Delta (in case of BFV). However, once we reach multiplicative level 0, we cannot do rescaling anymore. Therefore, in order to continue cipher-cipher multiplications, we need to restore the mutliplicative level to the original one. But the paper’s bootstrapping does not seem to support modulus restoration, but only resets the noise. Then, how come does this bootstrapping method make BFV a fully homomorphic encryption scheme? (from my understanding, the requirement of FHE is to support an indefinite number of addition/multiplication operations)
Yes, it can. Your understanding of BFV bootstrapping is incorrect.
In BFV, the pre-bootstrapping encrypted message (I am ignoring the mask for simplicity) is \lfloor q/t \rceil + e \bmod q. When we do bootstrapping (via evaluating the inner product by the encrypted secret using Q \gg q), we get a message \lfloor q/t^r \rceil + e' \bmod Q. Using digit extraction, we get down to \lfloor q/t \rceil + e'' \bmod Q', where Q' \ll Q, but Q' \gg q. Note that e'' can be reduced to e (using modulus). The fact that Q' \gg q gives one a lot of noise budget to do many (levels of) BFV multiplications. In other words, it is a proper bootstrapping procedure.
It says that initially we mod-switch from q \rightarrow p^e, do inner production, and then do digit extraction which changes its modulus from p^e \rightarrow p^r. Therefore, the modulus at the end of digit extraction is p^r, which is the plaintext modulus and is smaller than q.
In your description, I thought following mapping would hold:
Your Q means p^e
Your Q' means p^r
Your q is the lowest-level ciphertext modulus
But you said Q' \gg q, so my mapping above is somewhat wrong (because p^r < q). After we finish digit extraction with modulus p^r, how do you increase this modulus? Do you do another mod-switch to a larger modulus from p^r \rightarrow q_{\mathit{large}}?
Probably I understand now. Please correct me if I am wrong.
I think it’s not true that the ciphertext modulus changes from p^e \rightarrow p^r after homomorphic digit extraction, but the ciphertext modulus stays the same as p^e.
At line 6, when we divide y - w_{j, k + 1} by p, it’s not that we do modulus switch, but we keep the modulus the same (p^e) and only multiply by p^{-1}. Therefore, at the end of digit extraction, the modulus stays the same as p^e.
At the end of digit extraction, we have eliminated the entire noise and we have M \bmod p^e in the plaintext slot. Then, we homomorphically multiply by \dfrac{q}{p^r} to M (stored in the slots) to scale up the plaintext M to \Delta M = \dfrac{q}{p^r}M. Then, we do SlotToCoeff to move the plaintext values back to polynomial coefficients. Then, we get an encryption of polynomial \dfrac{q}{p^r}M + E', where E' is the new noise generated during homomorphic digit extraction of homomorphically evaluating the lifting polynomial F_e(X). After SlotToCoeff, we can do modulus switch from p^e \rightarrow q_L, where q_L is the highest multiplicative level’s modulus (we assume p^e > q_L).
