D-4.11 Modulus Bootstrapping

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

BGV’s bootstrapping shares some common aspects with both BFV and CKKS’s bootstrapping. The goal of BGV’s bootstrapping is the same as that of CKKS, but the internal technique is closer to that of BFV. Like CKKS, BGV’s bootstrapping resets the depleted ciphertext modulus from $q_l\to q_L$ (strictly speaking, from $q_l\to q_{l^{\prime }}$ such that $l<l^{\prime }<L$ because the bootstrapping operation itself consumes some multiplicative levels). This modulus transition effectively not only resets the multiplicative level but also reduces the noise-to-ciphertext modulus ratio. To achieve this goal, one might think that BGV’s bootstrapping can take the same ModRaise approach used by CKKS’s bootstrapping. However, this is not a directly applicable solution, because CKKS uses the sine approximation technique to eliminate the $q_0$-overflows after the mod-raise. On the other hand, BGV is an exact encryption scheme which does not allow approximation of plaintext values. Therefore, BGV uses BFV’s digit extraction approach to eliminate its modulus overflows. To use digit extraction, like in the case of BFV, BGV also has to modify the plaintext modulus to a specially prepared one, $p^{𝜀}$. To configure both the plaintext modulus and the ciphertext modulus to desired values (i.e., $p^{𝜀}$ and $q_L$), BGV uses the homomorphic decryption technique like BFV.

The technical details of BGV’s bootstrapping are as follows.

Suppose that we have an RLWE ciphertext $(A,B)={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(M)mod{q}_l$, where $A\cdot S+B=M+\mathrm{\Delta }E$, $\mathrm{\Delta }=t=p$ (a prime), and $q_l$ is the ciphertext modulus of the current multiplicative level.

1.

Modulus Switch from $q_l\to \widehat{q}$: BFV’s bootstrapping initially switches the ciphertext modulus from $q\to p^{𝜀-1}$ where $q\gg p^{𝜀}>t=p$. On the other hand, BGV’s bootstrapping switches the ciphertext modulus to $\widehat{q}$ that is a special modulus satisfying the relation: $\widehat{q}\equiv 1mod{p}^{𝜀}$ and $\widehat{q}>p^{𝜀}$ (where $p^{𝜀}$ will be explained in the next step). In order for a modulus switch from $q_l\to \widehat{q}$ (i.e., the special modulus) to be possible, the prime factor(s) comprising $\widehat{q}$ have to be congruent with $q_0,\cdots ,q_{L}modt$, so that we can do a modulus switch from $q_l\cdot \widehat{q}\to \widehat{q}$ (based on the technique learned in §D-4.7). Eventually, this step’s modulus switch transforms the ciphertext $(A,B)mod{q}_l$ to $(\widehat{A},\widehat{B})mod\widehat{q}$, during which the plaintext modulus (i.e., noise’s scaling factor) stays the same.

$$

2.

Ciphertext Coefficient Multiplication by $p^{𝜀-1}$: The constant $p^{𝜀-1}$ is multiplied to each coefficient of the ciphertext polynomials, updating the ciphertext to $p^{𝜀-1}\cdot (\widehat{A},\widehat{B})=(A^{\prime },B^{\prime })mod\widehat{q}$, where $A^{\prime }=p^{𝜀-1}\widehat{A}$ and $B^{\prime }=p^{𝜀-1}\widehat{B}$. This operation updates the original decryption relation $\widehat{A}\cdot S+\widehat{B}=M+\mathit{𝑝𝐸}+K\widehat{q}$ to $A^{\prime }\cdot S+B^{\prime }=p^{𝜀-1}M+p^{𝜀}E+K^{\prime }\widehat{q}$ (where $K^{\prime }=K\cdot p^{𝜀-1}$). Notice that the plaintext modulus (i.e., noise’s scaling factor) has been changed from $p\to p^{𝜀}$. When choosing $𝜀$, BGV enforces the following additional constraint: $\widehat{q}>p^{𝜀}$ and $\widehat{q}\equiv 1mod{p}^{𝜀}$.

$$

3.

ModRaise: We mod-raise $(\widehat{A},\widehat{B})mod\widehat{q}$ to $(\widehat{A},\widehat{B})mod{q}_L$, where $\widehat{q}\ll q_L$. The mod-raised ciphertext’s decryption relation is as follows:

$\widehat{A}\cdot S+\widehat{B}=p^{𝜀-1}M+p^{𝜀}E+K^{\prime }\widehat{q}mod{q}_L$

$$

Note that $K^{\prime }\widehat{q}$ is the $\widehat{q}$-multiple overflow and does not get reduced modulo $q_L$, because $K^{\prime }\widehat{q}\ll q_L$. We saw the same situation in the CKKS bootstrapping’s ModRaise (§D-3.13.1) which resets the ciphertext modulus from $q_0\to q_L$ at the cost of incurring a $K{q}_0$ overflow, which is to be removed by EvalExp’s homomorphic (approximate) sine graph evaluation (§D-3.13.4). Likewise, BGV’s mod-raised ciphertext $(\widehat{A},\widehat{B})mod{q}_L$ is ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(p^{𝜀-1}M+p^{𝜀}E+K^{\prime }\widehat{q})mod{q}_L$, an encryption of $p^{𝜀-1}M+p^{𝜀}E+K^{\prime }\widehat{q}$. In the later step, we will use digit extraction to homomorphically eliminate $K^{\prime }\widehat{q}$ like we did in BFV’s bootstrapping. The reason BGV’s bootstrapping uses digit extraction instead of approximated sine evaluation is that BGV is an exact encryption scheme like BFV (not an approximate scheme like CKKS).

$$

4.

CoeffToSlot: This step works the same way as CKKS and BFV’s CoeffToSlot step: move the coefficients of polynomial $p^{𝜀-1}M+p^{𝜀}E+\widehat{q}{K}^{\prime }$ to the input vector slots of a new ciphertext. We denote polynomial $Z=p^{𝜀-1}M+p^{𝜀}E+\widehat{q}{K}^{\prime }$, and each $i$-th coefficient of $Z$ as $z_i$. For the CoeffToSlot step, we homomorphically compute $Z\cdot n^{-1}\cdot \tilde{W}\cdot I_n^R$. Then, each input vector slot of the resulting ciphertext ends up storing each $z_i$ of the polynomial $Z$.

$$

5.

Digit Extraction: At this point, each input vector slot contains each coefficient of $p^{𝜀-1}M+p^{𝜀}E+\widehat{q}{K}^{\prime }$, which is $p^{𝜀-1}{m}_i+p^{𝜀}{e}_i+\widehat{q}{k}_i^{\prime }$. Recall that we designed the lowest multiplicative level’s ciphertext modulus $\widehat{q}$ and the homomorphic multiplication factor $p^{𝜀}$ such that $\widehat{q}\equiv 1mod{p}^{𝜀}$, or $\widehat{q}=k^{⟨\widehat{q}⟩}\cdot p^{𝜀}+1$ for some positive integer $k^{⟨\widehat{q}⟩}$. Therefore, the following holds:

$p^{𝜀-1}{m}_i+p^{𝜀}{e}_i+\widehat{q}{k}_i^{\prime }$

$=p^{𝜀-1}{m}_i+p^{𝜀}{e}_i+k_i^{\prime }\cdot (k^{⟨\widehat{q}⟩}\cdot p^{𝜀}+1)$ # applying $\widehat{q}=k^{⟨\widehat{q}⟩}\cdot p^{𝜀}+1$

$=p^{𝜀-1}{m}_i+k_i^{\prime }+p^{𝜀}\cdot (e_i+k_i^{\prime }\cdot k^{⟨\widehat{q}⟩})$ # rearranging the terms

$=p^{𝜀-1}{m}_i+k_i^{\prime }+p^{𝜀}\cdot k^{⟨\widehat{q}+𝜀⟩}$ # where $k^{⟨\widehat{q}+𝜀⟩}=e_i+k_i^{\prime }\cdot k^{⟨\widehat{q}⟩}$

$=p^{𝜀-1}{m}_i+k_i^{\prime }mod{p}^{𝜀}$

$$

To eliminate $k_i^{\prime }$ from the above, we will use the same digit extraction polynomial $G_{𝜀,v}$ as in BFV (§D-2.11.5) :

$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 }$ can be any integer, and $1\le {𝜀}^{\prime }\le w$

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

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

$$

We evaluate the digit extraction polynomial $G_{𝜀,v}$ for $v=\{𝜀-1,𝜀-2,\cdots ,1\}$ recursively total $𝜀-1$ times, at each coefficient $z_i$ of polynomial $Z$ stored at input vector slots. This operation finally zeros out the least significant (base-$p$) $𝜀-1$ digits of $z_i$ as follows:

$G_{𝜀,1}\circ G_{𝜀,2}\circ \cdots \circ G_{𝜀,𝜀-2}\circ G_{𝜀,𝜀-1}(z_i)mod{p}^{𝜀}$

$=p^{𝜀-1}{m}_{i}mod{p}^{𝜀}$

$=p^{𝜀-1}{m}_i+k_i^{″}{p}^{𝜀}$

$$

, where $k_i^{″}{p}^{𝜀}$ is some multiple of $p^{𝜀}$ to account for the original $p^{𝜀}$-overflow term plus an additional $p^{𝜀}$-overflows generated during the digit extraction. Note that the digit extraction step reduces the ciphertext modulus from $q_L\to q_{l^{\prime }}$ (where $l^{\prime }$ is an integer smaller than $L$), because the homomorphic evaluation of the polynomial $G_{𝜀,v}$ requires some ciphertext-to-ciphertext multiplications, which consume some multiplicative levels.

$$

6.

Homomorphic Multiplication by $p^{-(𝜀-1)}$: The output of the digit extraction step is $p^{𝜀-1}{m}_i+k_i^{″}{p}^{𝜀}$ stored in each input vector slot. We homomorphically multiply $|p^{-(𝜀-1)}{|}_{p^{𝜀}}$ to it, which is a modulo-$p^{𝜀}$ inverse of $p^{𝜀-1}$. Note that $p^{-(𝜀-1)}$ is guaranteed to exist because ${\mathbb{Z}}_{p^{𝜀}}$ is a finite field (i.e., Galois field) whose every element is guaranteed to have its counterpart inverse (Theorem A-3.1 in §A-3.1). Multiplying $p^{-(𝜀-1)}$ to $p^{𝜀-1}{m}_i+k^{″}i{p}^{𝜀}$ is equivalent to an exact division of $p^{𝜀-1}{m}_i+k^{″}i{p}^{𝜀}$ by $p^{𝜀-1}$, because $p^{𝜀-1}{m}_i+k^{″}i{p}^{𝜀}$ is exactly divisible by $p^{𝜀-1}$. We homomorphically compute the following:

$|p^{-(𝜀-1)}{|}_{p^{𝜀}}\cdot (p^{𝜀-1}{m}_i+k_i^{″}{p}^{𝜀})=m_i+k_i^{″}p(\mathit{𝑚𝑜𝑑}{p}^{𝜀})$

$$

Note that the plaintext value $m_i+k_i^{″}pmod{p}^{𝜀}$ is also equivalent to $m_i+k_i^{″}pmodp$ (because $p$ divides $p^{𝜀}$), and is also equivalent to $m_{i}modq$ (i.e., the message portion without the noise is $m_i$). Therefore, homomorphically multiplying $|p^{-(𝜀-1)}{|}_{p^{𝜀}}$ to a ciphertext that encrypts $p^{𝜀-1}{m}_i+k_i^{″}{p}^{𝜀}$ is equivalent to switching the plaintext modulus from $p^{𝜀}\to p$.

$$

In an alternative design, one can eliminate this step of homomorphic multiplication by $p^{-(𝜀-1)}$ by re-designing the digit extraction algorithm to gradually shift down the digits by total (base-$p$) $𝜀-1$ digits (by multiplying by $|p^{-1}{|}_{p^{𝜀}}$ at the end of each round of digit extraction).

$$

7.

SlotToCoeff: This step works the same way as BFV’s SlotToCoeff step: move $m_i+k_i^{″}p$ stored in the input vector slots back to the polynomial coefficient positions by homomorphically multiplying with ${\tilde{W}}^{\ast }$.

Meanwhile, the coefficient domain is in modulo $q_L$. From modulo-$q_L$’s perspective, the result of step 5 is $|p^{-(𝜀-1)}{|}_{p^{𝜀}}\cdot (p^{𝜀-1}{m}_i+k_i^{″}{p}^{𝜀})mod{q}_L$. It is guaranteed that $|p^{-(𝜀-1)}{|}_{p^{𝜀}}\cdot (p^{𝜀-1}{m}_i+k_i^{″}{p}^{𝜀})<q_L$, because $p^{𝜀}\ll q_L$. Therefore, result of SlotToCoeff is a set of polynomial coefficients whose noise is within the noise budget of $q_L$.

$$

8.

Noise Term Re-interpretation: The output of the SlotToCoeff step is ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(M+K^{″}p)mod{q}_{l^{\prime }}$, which also contains some noise term $E^{\prime }p$ generated during the homomorphic operations of step $2\sim 6$. Therefore, we can view the $K^{″}p$ term in the plaintext as part of the noise of the ciphertext. In other words, we can view ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(M+K^{″}p)$ with some noise term $E^{\prime }p$ as a ciphertext ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(M)$ with the noise term $E^{\prime }p+K^{″}p=(E^{\prime }+K^{″})\cdot p$. This step does not require any additional computation. The size of the coefficients of $K^{″}$ is upper-bounded because the operations of the CoeffToSlot, digit extraction, and SlotToCoeff steps are fixed. With a proper setup of the cryptographic parameters of BGV, we can guarantee that the noise-to-ciphertext modulus ratio always gets decreased after BGV’s bootstrapping (i.e., ${\displaystyle \frac{||E+K^{\prime }|{|}_{\infty }}{q_L}}<{\displaystyle \frac{||E^{\prime }+K^{″}|{|}_{\infty }}{q_{l^{\prime }}}}<{\displaystyle \frac{||E|{|}_{\infty }}{\widehat{q}}}$, where $\widehat{q}<q_l<q_{l^{\prime }}<q_L$, and $||P|{|}_{\infty }$ denotes the maximum absolute coefficient value of polynomial $P$).

D-4.11.1 The Reason for Modulus Switch from $q_l\to \widehat{q}$

BGV switches the modulus from $q_l\to \widehat{q}$ to eliminate the $q_l$-multiple overflows during bootstrapping. After switching the modulus $q_l\to \widehat{q}$ and then ModRaise, the encrypted plaintext gets the $K^{\prime }\widehat{q}$ overflow term, which can be reduced to $K^{\prime }$ from the plaintext modulus’s perspective due to the special property $\widehat{q}\equiv 1mod{p}^{𝜀}$ (where $p^{𝜀}$ is the plaintext modulus).

D-4.11.2 ModRaise instead of Homomorphic Decryption

In the case of BFV’s bootstrapping, we need homomorphic decryption (§D-2.11.3) because we need to simultaneously change the ciphertext’s plaintext scaling factor from $p^{𝜀-1}\to \lfloor {\displaystyle \frac{q}{p}}\rfloor$ and the ciphertext modulus from $p^{𝜀}\to q$. On the other hand, in the case of CKKS’s bootstrapping, ModRaise instead of homomorphic decryption is sufficient because we only need to change the ciphertext modulus from $q_0\to q_L$ while keeping the same plaintext scaling factor $\mathrm{\Delta }\approx {\displaystyle \frac{q_l}{q_{l-1}}}$. Similarly, in the case of BGV’s bootstrapping, ModRaise instead of homomorphic decryption is sufficient because we only need to change the ciphertext modulus from $\widehat{q}\to q_L$ while keeping the noise scaling factor (i.e., the plaintext modulus) $\mathrm{\Delta }=p^{𝜀}$.

D-4.11.3 The Choice of $𝜀$

The larger $𝜀$ is, the greater the (base-$p$) digit-wise gap between $p^{𝜀-1}M$ and $K^{\prime }$ becomes, and thus the less likely it is that the decryption would fail (i.e., fail to zero out $K^{\prime }$). But a larger $𝜀$ means the digit extraction operation would be more expensive.

D-4.11.4 Generalization to $\mathrm{\Delta }=p^r$

Like the case of BFV’s bootstrapping (Summary D-2.11.7 in §D-2.11.7), we can generalize the plaintext modulus (i.e., noise scaling factor) to $p^r$ where $p$ is a prime and $r$ can be any positive integer.