Ciphertext-to-Ciphertext Multiplication

Since BGV uses a leveled ciphertext modulus chain like CKKS, BGV’s ciphertext-to-ciphertext multiplication scheme is exactly the same as CKKS’s scheme (Summary D-3.5 in §D-3.5), except for the rescaling step which uses BGV’s modulus switch (§D-4.7).

$⟨$ Summary D-4.8 $⟩$ BGV Ciphertext-to-Ciphertext Multiplication

Suppose we have the following two RLWE ciphertexts:

${𝖱𝖫𝖶𝖤}_{S, σ} (M^{⟨ 1 ⟩} + Δ E^{⟨ 1 ⟩}) = (A^{⟨ 1 ⟩}, B^{⟨ 1 ⟩})$ , where $B^{⟨ 1 ⟩} = - A^{⟨ 1 ⟩} \cdot S + M^{⟨ 1 ⟩} + Δ E^{⟨ 1 ⟩}$

${𝖱𝖫𝖶𝖤}_{S, σ} (M^{⟨ 2 ⟩} + Δ E^{⟨ 2 ⟩}) = (A^{⟨ 2 ⟩}, B^{⟨ 2 ⟩})$ , where $B^{⟨ 2 ⟩} = - A^{⟨ 2 ⟩} \cdot S + M^{⟨ 2 ⟩} + Δ E^{⟨ 2 ⟩}$

Multiplication between these two ciphertexts is performed as follows:

1.

Basic Multiplication

Compute the following:

$D_{0} = B^{⟨ 1 ⟩} \cdot B^{⟨ 2 ⟩}$

$D_{1} = A^{⟨ 1 ⟩} \cdot B^{⟨ 2 ⟩} + A^{⟨ 2 ⟩} \cdot B^{⟨ 1 ⟩}$

$D_{2} = A^{⟨ 1 ⟩} \cdot A^{⟨ 2 ⟩}$

The decryption relation satisfies: $M^{⟨ 1 ⟩} M^{⟨ 2 ⟩} + Δ \cdot (M^{⟨ 1 ⟩} E^{⟨ 2 ⟩} + M^{⟨ 2 ⟩} E^{⟨ 1 ⟩}) + Δ^{2} E^{⟨ 1 ⟩} E^{⟨ 2 ⟩}$

$= \underset{D_{0}}{\underset{⏟}{B^{⟨ 1 ⟩} \cdot B^{⟨ 2 ⟩}}} + \underset{D_{1}}{\underset{⏟}{(B^{⟨ 2 ⟩} \cdot A^{⟨ 1 ⟩} + B^{⟨ 1 ⟩} \cdot A^{⟨ 2 ⟩})}} \cdot S + \underset{D_{2}}{\underset{⏟}{(A^{⟨ 1 ⟩} \cdot A^{⟨ 2 ⟩})}} \cdot \underset{S^{2}}{\underset{⏟}{S \cdot S}}$

$= D_{0} + D_{1} \cdot S + D_{2} \cdot S^{2}$

2.

Relinearization

${𝖱𝖫𝖶𝖤}_{S, σ} (M^{⟨ 1 ⟩} M^{⟨ 2 ⟩} + Δ \cdot (M^{⟨ 1 ⟩} E^{⟨ 2 ⟩} + M^{⟨ 2 ⟩} E^{⟨ 1 ⟩}) + Δ^{2} E^{⟨ 1 ⟩} E^{⟨ 2 ⟩})$

$= {𝖱𝖫𝖶𝖤}_{S, σ} (D_{0} + D_{1} \cdot S + D_{2} \cdot S^{2})$

$\approx C_{α} + C_{β}, where C_{α} = (D_{1}, D_{0}), C_{β} = ⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (D_{2}), {𝖱𝖫𝖾𝗏}_{S, σ}^{β, l} (S^{2}) ⟩$

3.

(Optional) Rescaling

To suppress the noise component scaled by $Δ^{2}$ and return it to a factor of $Δ$ , switch the ciphertext’s modulo from $q \to \hat{q}$ by updating $(A, B)$ to $(\hat{A}, \hat{B})$ according to BGV’s modulus switch explained in Summary D-4.7 (§D-4.7).

After the above update of $(A, B)$ to $(\hat{A}, \hat{B})$ , the noise scaling factor $Δ = t$ and the plaintext $M$ stay the same, as we proved in §D-4.7 that $((\hat{A} \cdot S + \hat{B}) mod \hat{q}) mod t = M$ .

Swapping the Order of Relinearization and Rescaling: The order of relinearization and rescaling is interchangeable. Running rescaling before relinearization reduces the size of the ciphertext modulus, and therefore the subsequent relinearization can be executed faster.

Details of the Optional Rescaling: Before rescaling, the contents of the ciphertext are

M^{⟨ 1 ⟩} M^{⟨ 2 ⟩} + Δ \cdot (M^{⟨ 1 ⟩} E^{⟨ 2 ⟩} + M^{⟨ 2 ⟩} E^{⟨ 1 ⟩}) + Δ^{2} E^{⟨ 1 ⟩} E^{⟨ 2 ⟩} + 𝜖

, where

𝜖

is a relinearization error. Therefore, after each ciphertext-to-ciphertext multiplication, the noise’s scaling factor will become squared as

Δ^{2}, Δ^{4}, Δ^{8}, \dots

. To reduce such exponential noise growth rate, we can optionally rescale down the ciphertext by

w_{l} = \frac{q_{l}}{q_{l - 1}} > Δ

at the end of each relinearization at multiplicative level

l

, which is the noise’s growth rate (effectively keeping the noise scaling factor as

Δ

). After rescaling, the ciphertext gets scaled down by

w_{l}

and then added by a new noise

𝜖_{2}

. Before the rescaling, the noise grew roughly by the factor of

Δ = t

(as the largest noise term is

Δ^{2} E^{⟨ 1 ⟩} E^{⟨ 2 ⟩}

), but the rescaling process reduces this growth rate by the factor of

w_{l}

and then introduces a new constant noise

𝜖_{2}

. Therefore, if

w_{l}

is sufficiently bigger than

Δ = t

, the resulting noise will decrease compared to both

Δ E^{⟨ 1 ⟩}

and

Δ E^{⟨ 2 ⟩}

. Due to this reason, when we design the modulus chain of BGV, we require each

w_{l}

to be sufficiently bigger than

Δ = t

to effectively reduce the noise growth rate upon each ciphertext-to-ciphertext multiplication (while ensuring the property that its reduction modulo

t

gives the plaintext

M

as explained in §D-4.7). Meanwhile, the constant noise term

𝜖_{2}

gets newly added upon each rescaling, but this term becomes part of the rescaled ciphertext, which will be later reduced by the factor of

w_{l - 1}

in the future rescaling. Therefore, BGV’s rescaling upon ciphertext-to-ciphertext multiplication effectively suppresses the noise growth.

On the other hand, the above design strategy of noise reduction is inapplicable to CKKS, because in CKKS, we use the scaling factor

Δ

to scale the message

M

(not the noise

E

), and thus CKKS requires each

w_{l} \approx Δ

in order to preserve the plaintext’s scaling factor

Δ

as the same value across ciphertext-to-ciphertext multiplications. Because of this difference in design, CKKS inevitably increases the noise after each ciphertext-to-ciphertext multiplication.

D-4.8 Ciphertext-to-Ciphertext Multiplication