Encryption and Decryption

BGV’s encryption and decryption scheme is very similar to BFV’s scheme (Summary D-2.3 in §D-2.3) with a small difference: while BFV scales the plaintext polynomial

M (X)

Δ

, BGV scales the noise polynomial

E (X)

Δ

. In BFV, each encoded plaintext polynomial

M (X)

is scaled by

Δ = ⌊ \frac{q}{t} ⌋

. This strategy effectively shifts each plaintext coefficient value to the most significant bits while keeping the noise in the least significant bits. On the other hand, BGV does not scale the plaintext polynomial

M (X)

, but instead it scales each new noise

E (X)

Δ = t

, making the noise

Δ E (X)

, which is newly generated upon each new ciphertext creation. This different scaling strategy effectively shifts the noise (i.e.,

e_{i}

) to the most significant bits by scaling it by

Δ = t

while keeping the plaintext value (i.e.,

m_{i}

)

M (X)

’s each coefficient in the least significant bits.

Also, in BGV, the ciphertext modulus

q

is leveled like CKKS’s one:

q \in {q_{0}, q_{1}, \dots, q_{L}}

, where each

q_{l} = \prod_{i = 0}^{l} w_{i}

(where each

w_{i}

is a CRT modulus).

$⟨$ Summary D-4.2 $⟩$ BGV Encryption and Decryption

Initial Setup:

The plaintext modulus $t = p$ (a prime)
The ciphertext modulus $q$ is leveled like in CKKS: $q \in {q_{0}, q_{1}, \dots, q_{L}}$ , where each $q_{l} = \prod_{i = 0}^{l} w_{i}$ (each $w_{i}$ is a CRT modulus), and each $q_{l} \equiv 1 mod t$ (will be explained in §D-4.7)
The noise scaling factor $Δ = t$
The secret key $S \leftarrow_{}^{$} R_{⟨ n, 2 ⟩}$ . They coefficients of polynomial $S$ can be either binary (i.e., ${0, 1}$ ) or ternary (i.e., ${- 1, 0, 1}$ ).

Encryption Input: $M \in R_{⟨ n, q ⟩}$ , $A \leftarrow_{}^{$} R_{⟨ n, q ⟩}$ , $E \leftarrow_{}^{χ_{σ}} R_{⟨ n, q ⟩}$

1.: Compute $B = - A \cdot S + M + Δ E \in R_{⟨ n, q ⟩}$
2.: ${𝖱𝖫𝖶𝖤}_{S, σ} (M + Δ E) = (A, B) \in R_{⟨ n, q ⟩}^{2}$

Decryption Input: $C = (A, B) \in R_{⟨ n, q ⟩}^{2}$

1.: ${𝖱𝖫𝖶𝖤}_{S, σ}^{- 1} (C) = B + A \cdot S = M + Δ E (𝑚𝑜𝑑 q)$
2.: $M = M + Δ E mod t$ # modulo reduction of $M + Δ E$ by $t$

The final output is $M (X) \in ℤ_{t} [X] ∕ (X^{n} + 1)$

Conditions for Correct Decryption:

Each coefficient $Δ e_{i} + m_{i}$ that contains the scaled noise and the plaintext should not overflow or underflow its ciphertext’s any current moment’s multiplicative level $l$ ’s ciphertext modulus $q_{l}$ (i.e., $Δ e_{i} + m_{i} < q_{l}$ )

When restoring the plaintext at the end of the decryption process, while BFV shifts down the plaintext and the noise to the lower bit area (which effectively rounds off the noise), BGV computes

mod p

, which effectively modulo-reduces the accumulated noise because every coefficient of

E

is a multiple of

t

(i.e.,

Δ

). Finally, only the plaintext polynomial’s each coefficient

m_{i}

remains in the low-digit area without any noise

e_{i}

D-4.2 Encryption and Decryption