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, 𝑡𝑒𝑟𝑛 ⟩}$

, 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 are 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 + E) = (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:

As explained in Summary B-2.3.1 (in §B-2.3.1), the noise bound is $| - 𝜖 k_{i} t + e_{i} | < \frac{Δ}{2}$ , where $k_{i}$ is each coefficient of the polynomial $K$ that accounts for the $t$ -multiple overflows of the coefficients of the plaintext polynomial updated across homomorphic operations.

In this section, we will often write

{𝖱𝖫𝖶𝖤}_{S, σ} (Δ M + E)

{𝖱𝖫𝖶𝖤}_{S, σ} (Δ M)

for simplicity, because

{𝖱𝖫𝖶𝖤}_{S, σ} (Δ M + E) \approx {𝖱𝖫𝖶𝖤}_{S, σ} (Δ M)

(i.e., they decrypt to the same message). Even in the case that we write

{𝖱𝖫𝖶𝖤}_{S, σ} (Δ M)

instead of

{𝖱𝖫𝖶𝖤}_{S, σ} (Δ M + E)

, you should assume this as an encryption of

Δ M + E

(i.e., the noise is included inside the scaled message).

We will explain the conditions for BFV’s correct decryption in more detail in §D-2.4.1.

D-2.3 Encryption and Decryption