Encryption and Decryption

BFV encrypts and decrypts ciphertexts based on the RLWE cryptosystem (§B-3) with the sign of each

A \cdot S

term flipped in the encryption and decryption formula. Specifically, this is equivalent to the alternative version of the GLWE cryptosystem (§B-4.4) with

k = 1

. Thus, BFV’s encryption and decryption formulas are as follows:

$⟨$ Summary D-2.3 $⟩$ BFV Encryption and Decryption

Initial Setup: $Δ = ⌊ \frac{q}{t} ⌋ is a plaintext scaling factor for polynomial encoding, S \leftarrow_{}^{$} R_{⟨ n, 2 ⟩}$

, where plaintext modulus $t$ is either a prime ( $p$ ) or a power of prime ( $p^{r}$ ), and ciphertext modulus $q ≫ t$ . As for the coefficients of polynomial $S$ , they can be either binary (i.e., ${0, 1}$ ) or ternary (i.e., ${- 1, 0, 1}$ ).

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

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

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

${𝖱𝖫𝖶𝖤}_{S, σ}^{- 1} (𝖼𝗍) = ⌈ \frac{B + A \cdot S mod q}{Δ} ⌋ mod t = ⌈ \frac{Δ M + E}{Δ} ⌋ mod t = M mod t$

(The noise $E = \sum_{i = 0}^{n - 1} e_{i} X^{i}$ gets eliminated by the rounding process)

Conditions for Correct Decryption:

1.: Each noise coefficient $e_{i}$ growing during homomorphic operations should never exceed: $e_{i} < \frac{Δ}{2}$ .
2.: Each plaintext coefficient $m_{i}$ being updated across homomorphic operations should never overflow or underflow $q$ (i.e., $m_{i} < q$ )
3.: The specific noise bound is as explained in §B-2.3.1:
$\frac{k_{i} t + e_{i}}{⌊ \frac{q}{t} ⌋} < \frac{1}{2}$ # $k_{i} t$ accounts for the plaintext $m_{i}$ ’s wrapped-around value as multiples of $t$

D-2.3 Encryption and Decryption