Modulus Bootstrapping

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^{'}}$ such that $l < l^{'} < L$ because the bootstrapping operations between step 2 $\sim$ 6 have consumed 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}$ -multiple overflows after the mod-raise. On the other hand, BGV is an exact encryption scheme that does not allow the approximation of plaintext values. Therefore, BGV uses BFV’s digit extraction approach to eliminate its modulus overflows. To use digit extraction, as 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 the desired values (i.e., $p^{𝜀}$ and $q_{L}$ ), BGV employs the homomorphic decryption technique, as BFV does.

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

Suppose that we have an RLWE ciphertext $(A, B) = {𝖱𝖫𝖶𝖤}_{S, σ} (M + Δ E) mod q_{l}$ , where $A \cdot S + B = M + Δ E$ , $Δ = t = p$ (a prime), and $q_{l}$ is the ciphertext modulus of the current multiplicative level.

1.

Modulus Switch from

q_{l} \to \hat{q}

: BFV’s bootstrapping initially switches the ciphertext modulus from

q \to p^{𝜀 - 1}

where

q ≫ p^{𝜀} > t = p

. On the other hand, BGV’s bootstrapping switches the ciphertext modulus to

\hat{q}

that is a special modulus satisfying the relation:

\hat{q} \equiv 1 mod p^{𝜀}

and

\hat{q} > p^{𝜀}

(where

p^{𝜀}

will be explained in the next step). In order for a modulus switch from

q_{l} \to \hat{q}

(i.e., the special modulus) to be possible, the prime factor(s) comprising

\hat{q}

have to be congruent with

q_{0}, \dots, q_{L} mod t

, so that we can do a modulus switch from

q_{l} \cdot \hat{q} \to \hat{q}

(based on the technique learned in §D-4.7). Eventually, this step’s modulus switch transforms the ciphertext

(A, B) mod q_{l}

(\hat{A}, \hat{B}) mod \hat{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 (\hat{A}, \hat{B}) = (A^{'}, B^{'}) mod \hat{q}

, where

A^{'} = p^{𝜀 - 1} \hat{A}

and

B^{'} = p^{𝜀 - 1} \hat{B}

. This operation updates the original decryption relation

\hat{A} \cdot S + \hat{B} = M + 𝑝𝐸 + K \hat{q}

A^{'} \cdot S + B^{'} = p^{𝜀 - 1} M + p^{𝜀} E + K^{'} \hat{q}

(where

| | K^{'} | |_{\infty} \leq n + 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:

\hat{q} > p^{𝜀}

and

\hat{q} \equiv 1 mod p^{𝜀}

3.

ModRaise: We mod-raise

(\hat{A}, \hat{B}) mod \hat{q}

(\hat{A}, \hat{B}) mod q_{L}

, where

\hat{q} ≪ q_{L}

. The mod-raised ciphertext’s decryption relation is as follows:

$\hat{A} \cdot S + \hat{B} = p^{𝜀 - 1} M + p^{𝜀} E + K^{'} \hat{q} mod q_{L}$

Note that $K^{'} \hat{q}$ is the $\hat{q}$ -multiple overflow and does not get reduced modulo $q_{L}$ , because $K^{'} \hat{q} ≪ 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 $(\hat{A}, \hat{B}) mod q_{L}$ is ${𝖱𝖫𝖶𝖤}_{S, σ} (p^{𝜀 - 1} M + p^{𝜀} E + K^{'} \hat{q}) mod q_{L}$ , an encryption of $p^{𝜀 - 1} M + p^{𝜀} E + K^{'} \hat{q}$ . In the later step, we will use digit extraction to homomorphically eliminate $K^{'} \hat{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 the polynomial

p^{𝜀 - 1} M + p^{𝜀} E + \hat{q} K^{'}

to the input vector slots of a new ciphertext. We denote polynomial

Z = p^{𝜀 - 1} M + p^{𝜀} E + \hat{q} K^{'}

, and each

i

-th coefficient of

Z

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 + \hat{q} K^{'}

, which is

p^{𝜀 - 1} m_{i} + p^{𝜀} e_{i} + \hat{q} k_{i}^{'}

. Recall that we designed the lowest multiplicative level’s ciphertext modulus

\hat{q}

and the homomorphic multiplication factor

p^{𝜀}

such that

\hat{q} \equiv 1 mod p^{𝜀}

, or

\hat{q} = k^{⟨ \hat{q} ⟩} \cdot p^{𝜀} + 1

for some positive integer

k^{⟨ \hat{q} ⟩}

. Therefore, the following holds:

$p^{𝜀 - 1} m_{i} + p^{𝜀} e_{i} + \hat{q} k_{i}^{'}$

$= p^{𝜀 - 1} m_{i} + p^{𝜀} e_{i} + k_{i}^{'} \cdot (k^{⟨ \hat{q} ⟩} \cdot p^{𝜀} + 1)$ $▹$ applying $\hat{q} = k^{⟨ \hat{q} ⟩} \cdot p^{𝜀} + 1$

$= p^{𝜀 - 1} m_{i} + k_{i}^{'} + p^{𝜀} \cdot (e_{i} + k_{i}^{'} \cdot k^{⟨ \hat{q} ⟩})$ $▹$ rearranging the terms

$= p^{𝜀 - 1} m_{i} + k_{i}^{'} + p^{𝜀} \cdot k_{i}^{⟨ \hat{q} + 𝜀 ⟩}$ $▹$ where $k_{i}^{⟨ \hat{q} + 𝜀 ⟩} = e_{i} + k_{i}^{'} \cdot k^{⟨ \hat{q} ⟩}$

$\equiv p^{𝜀 - 1} m_{i} + k_{i}^{'} (𝑚𝑜𝑑 p^{𝜀})$

To eliminate $k_{i}^{'}$ from the above (where $| k_{i}^{'} | \leq n + 1$ ), we use the same digit extraction polynomial $G_{𝜀, v}$ as in the BFV bootstrapping (§D-2.11.5) :

$z_{i} = d_{0} + (\sum_{j = 𝜀^{'}}^{𝜀 - 1} d_{*} p^{j})$ $▹$ where $d_{0} \in ℤ_{p}$ , and $d_{*}$ can be any integer, and $1 \leq 𝜀^{'} \leq 𝜀$

$F_{𝜀^{'}} (z_{i}) \equiv d_{0} mod p^{𝜀^{'} + 1}$

$G_{𝜀} (z_{i}) \equiv (z_{i} - \underset{𝜀 - 1 times}{\underset{⏟}{F_{𝜀 - 1} \circ F_{𝜀 - 2} \circ \dots \circ F_{1}}} (z_{i})) \cdot | p^{- 1} |_{q}$

We evaluate the digit extraction polynomial $G_{𝜀}$ for ${𝜀, 𝜀 - 1, 𝜀 - 2, \dots, 2}$ recursively a total of $𝜀 - 1$ times. This operation finally zeros out and right-shifts the least significant (base- $p$ ) $𝜀 - 1$ digits of $z_{i}$ as follows:

$G_{2} \circ G_{3} \circ \dots \circ G_{𝜀 - 1} \circ G_{𝜀} (z_{i})$

$= m_{i} + k_{i}^{″} p mod q_{l^{'}}$

, where $k_{i}^{″} p^{𝜀}$ is some multiple of $p^{𝜀}$ to account for the original $p^{𝜀}$ -multiple overflow term plus additional $p^{𝜀}$ -multiple overflows generated during the digit extraction. Note that the digit extraction step reduces the ciphertext modulus from $q_{L} \to q_{l^{'}}$ (where $l^{'}$ is an integer smaller than $L$ ), because the homomorphic evaluation of the polynomial $G_{𝜀}$ requires some ciphertext-to-ciphertext multiplications, which consume some multiplicative levels. The output of the digit extraction step is $m_{i} + k_{i}^{″} p mod q_{l^{'}}$ stored in each input vector slot.

Handling the Divisions by $p$ : Unlike in BFV (§D-2.11.5), we cannot use scaling factor re-interpretation because the scaling factor setup of BGV is different from that of BFV. In BGV’s digit extraction, each round should explicitly homomorphically multiply the slot values by $| p^{- 1} |_{q^{⟨ i ⟩}}$ , where $q^{⟨ i ⟩}$ is the ciphertext modulus at the $i$ -th round of digit extraction. Given $(A^{⟨ g_{1} ⟩}, B^{⟨ g_{1} ⟩}) mod q^{⟨ 1 ⟩}$ is the ciphertext at the 1st round of digit extraction just before inverse- $p$ division, the actual division-by- $p$ is equivalent to performing the ciphertext-to-plaintext multiplication (§D-2.6) as follows:

$(A^{⟨ g_{1} ⟩}, B^{⟨ g_{1} ⟩}) \cdot 𝖤𝗇𝖼𝗈𝖽𝖾 (p^{- 1}) mod q^{⟨ 1 ⟩}$

$= (A^{⟨ g_{1} ⟩}, B^{⟨ g_{1} ⟩}) \cdot p^{- 1} mod q^{⟨ 1 ⟩}$ $▹$ since $𝖤𝗇𝖼𝗈𝖽𝖾 (p^{- 1}) = p^{- 1} + 0 X + 0 X^{2} + \dots + 0 X^{n - 1}$

$= (p^{- 1} A^{⟨ g_{1} ⟩}, p^{- 1} B^{⟨ g_{1} ⟩}) mod q^{⟨ 1 ⟩}$

Therefore, by multiplying the coefficients of two BGV ciphertext polynomials $A^{⟨ g_{1} ⟩}$ and $B^{⟨ g_{1} ⟩}$ by $| p^{- 1} |_{q^{⟨ 1 ⟩}}$ , we obtain the following effect:

$(| p^{- 1} |_{q^{⟨ 1 ⟩}} \cdot A^{⟨ g_{1} ⟩}) \cdot S + (| p^{- 1} |_{q^{⟨ 1 ⟩}} \cdot B^{⟨ g_{1} ⟩}) mod q^{⟨ 1 ⟩}$

$= | p^{- 1} |_{q^{⟨ 1 ⟩}} \cdot (p^{𝜀 - 1} M + {⌊ K^{'} ⌋}_{p} + K^{″} p^{𝜀}) mod q^{⟨ 1 ⟩}$

$= p^{𝜀 - 2} M + ⌊ \frac{K^{'}}{p} ⌋ + K^{″} p^{𝜀 - 1} mod q^{⟨ 1 ⟩}$

Verbally speaking, the above inverse- $p$ multiplication to all polynomial coefficients of $(A^{⟨ g_{1} ⟩}, B^{⟨ g_{2} ⟩})$ has the following two effects: (1) scales down the plaintext and the noise by $p$ ; and (2) reduces the modulus garbage term $K^{'}$ to $⌊ \frac{K^{'}}{p} ⌋$ (i.e., right-shift by 1 base- $p$ digit).

BGV’s digit extraction procedure is equivalent to recursively evaluating $G_{𝜀}$ with the input $z_{i}$ by decreasing $𝜀$ by 1 at each round (total $𝜀 - 1$ rounds) as follows:

Input: $p^{𝜀 - 1} M + K^{'} + K^{″} p^{𝜀} mod \hat{q}$

1st Round: $G_{𝜀} (z_{i}) {==\Rightarrow}_{}^{effect} p^{𝜀 - 2} M + ⌊ \frac{K^{'}}{p} ⌋ + {K^{″}}^{⟨ 1 ⟩} p^{𝜀 - 1} mod q^{⟨ 1 ⟩}$

2nd Round: $G_{𝜀 - 1} \circ G_{𝜀} (z_{i}) {==\Rightarrow}_{}^{effect} p^{𝜀 - 3} M + ⌊ \frac{K^{'}}{p^{2}} ⌋ + {K^{″}}^{⟨ 2 ⟩} p^{𝜀 - 2} mod q^{⟨ 2 ⟩}$

3rd Round: $G_{𝜀 - 2} \circ G_{𝜀 - 1} \circ G_{𝜀} (z_{i}) {==\Rightarrow}_{}^{effect} p^{𝜀 - 4} M + ⌊ \frac{K^{'}}{p^{3}} ⌋ + {K^{″}}^{⟨ 3 ⟩} p^{𝜀 - 3} mod q^{⟨ 3 ⟩}$

$⋮$

$𝜀 - 1$ -th Round: $G_{2} \circ \dots \circ G_{𝜀} (z_{i}) {==\Rightarrow}_{}^{effect} M + {K^{″}}^{⟨ 𝜀 - 1 ⟩} p mod q^{⟨ 𝜀 - 1 ⟩}$

As shown above, the entire digit extraction procedure results in two effects on the values stored in the plaintext slots: (1) scales down the message $p^{𝜀 - 1} M$ to $M$ ; and (2) zeros out the modulus garbage $K^{'}$ (i.e., $⌊ \frac{K^{'}}{p^{𝜀 - 1}} ⌋ = 0$ ). The reason why $K^{″}$ gets updated to ${K^{″}}^{⟨ 1 ⟩}, {K^{″}}^{⟨ 2 ⟩}, \dots, {K^{″}}^{⟨ 𝜀 - 1 ⟩}$ across rounds is that each $i$ -th round’s evaluation of function $F_{𝜖^{'}}$ and $G_{𝜖}$ is done modulo $p^{𝜀 - i}$ , which produces new $p^{𝜀 - i}$ -multiple overflow garbage values each time.

Beneficially, the $𝜀 - 1$ rounds of inverse- $p$ multiplications yields the effect of scaling down the plaintext $p^{𝜀 - 1} m_{i} \to m_{i}$ and the noise $k^{″} p^{𝜀} \to k^{″} p$ , which has the desired noise scaling factor $p$ for standard BGV ciphertexts.

6.

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}}^{*}

. Upon completing this step, the ciphertext modulus is some value

q_{l^{'}}

smaller than

q_{L}

, because the homomorphic operation of step

4 \sim 6

has consumed a few multiplicative levels. The resulting plaintext coefficients are

m_{i} + k_{i}^{‴} p

, where

k^{‴} > k^{″}

due to the additional noise generated by homomorphically running the SlotToCoeff step. The plaintext modulus (i.e., the noise scaling factor) and the noise scaling factor are

p

at this point, the standard one for BGV ciphertexts. We let these polynomials be

M

and

K^{‴}

each, and the output ciphertext is

{𝖱𝖫𝖶𝖤}_{S, σ} (M + K^{‴} p) mod q_{l^{'}}

D-4.11.1 Discussion

The Reason for Modulus Switch from $q_{l} \to \hat{q}$ : BGV switches the modulus from $q_{l} \to \hat{q}$ to eliminate the $q_{l}$ -multiple overflows during bootstrapping. After switching the modulus $q_{l} \to \hat{q}$ and then ModRaise, the encrypted plaintext gets the $K^{'} \hat{q}$ overflow term, which can be reduced to $K^{'}$ from the plaintext modulus’s perspective due to the special property $\hat{q} \equiv 1 mod p^{𝜀}$ (where $p^{𝜀}$ is the plaintext modulus).

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

Generalization to $Δ = p^{r}$ : Like the case of BFV’s bootstrapping (Summary D-2.11.6 in §D-2.11.6), 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.

D-4.11.2 Comparing the Bootstrapping in BFV, BGV, and CKKS

Both BFV and BGV’s bootstrapping use digit extraction, but for different purposes. In BFV, digit extraction is used to eliminate the noise in the lower-bit area. In BGV, digit extraction is used to eliminate the modulus garbage values in the lower-bit area generated by ModRaise from $\hat{q} \to q_{L}$ . In addition, at each round of BGV’s digit extraction, we explicitly multiply the coefficients of the ciphertext polynomials by $| p^{- 1} |_{q^{⟨ i ⟩}}$ . In BFV, this explicit inverse- $p$ multiplication is skipped and we only conceptually re-interpret the scaling factor.

CKKS’s bootstrapping does not involve digit extraction because it has no values to eliminate in the lower-bit area. Instead, regarding the modulus garbage value ModRaise from $q_{0} \to q_{L}$ , this is eliminated by EvalExp’s homomorphic evaluation of an approximate sine function. Although CKKS’s bootstrapping resets its modulus to a large value, this operation does not decrease the noise-to-message ratio, and this ratio continuously increases over homomorphic operations.

[prev][parent]