Part 4: BFV Scheme | Building Blocks of FHE

The BFV (Brakerski/Fan-Vercauteren) and BGV (Brakerski-Gentry-Vaikuntanathan) encryption schemes are important steps forward in encryption technology. They build on the idea of Fully Homomorphic Encryption (FHE), which allows data to be processed while still encrypted. This means we can perform calculations on secure data without needing to decrypt it first. These schemes are practical and useful for keeping data safe during processing, especially in areas like secure communication and privacy-protecting data analysis.

What Is BFV Encryption?

The BFV scheme is recognized as part of the second generation of FHE schemes, built upon the Ring Learning with Errors (RLWE) problem.

BFV operates over two distinct rings: the plaintext ring and the ciphertext ring.

Like other FHE schemes, BFV enables an untrusted party to perform meaningful computations on encrypted data without requiring access to the decryption key.‍

Fundamentals

Key Generation

$KeyGen()$ takes as input some encryption parameters and returns a set of keys:

1. the secret key ($sk$),
2. the public key ($pk$),
3. the evaluation key ($ek$).

Encryption

$Enc()$ takes as input $pk$ and a plaintext message $m \in M$, and returns a valid ciphertext $c \in C$.

Decryption

$Dec()$ takes as input $sk$ and a valid ciphertext, and returns $m$.

Addition

$Add()$ takes some encryption parameters, $ek$, and two ciphertexts $(c_1, c_2)$, and returns a valid ciphertext $c_3$ encrypting $m_1 + m_2$ where $c_1$ and $c_2$ encrypt $m_1$ and $m_2$, respectively.

Multiplication

$Mul()$ takes some encryption parameters, $ek$, and two ciphertexts $(c_1, c_2)$, and returns a valid ciphertext $c_3$ encrypting $m_1 \cdot m_2$ where $c_1$ and $c_2$ encrypt $m_1$ and $m_2$, respectively.

Plaintext & Ciphertext Spaces

The plaintext space $P$ is defined over a polynomial ring:

$$P = R_t = \mathbb{Z}_t[x]/(x^n + 1)$$

The ciphertext space $C$ is also defined over a polynomial ring:

$$C = R_q \times R_q$$

where $R_q = \mathbb{Z}_q[x]/(x^n + 1)$, $n \in \mathbb{Z}$ is the dimension. Note that, practically, $q >> t$.

Message Encoding & Decoding

One of the well-known encoding schemes is the “integer encoding scheme” which works as follows:

1. Represent the message in binary representation:

$$a_{n-1} a_{n-2} … a_2 a_1 a_0$$

2. Compose:

$$m = a_{n-1} x^{n-1} + a_{n-2} x^{n-2} + … + a_2 x^2 + a_1 x + a_0$$

As $n$ is large in general, we set unused bits to 0.

Key Generation

We generate the secret key $sk$ as a random polynomial from $R_2$, a polynomial of degree $n$ with coefficients in $\{ -1, 0, 1 \}$.

Then we calculate the corresponding public key  $pk = (pk_1, pk_2)$ as follows:

$$pk_1 = -1 \cdot (a \cdot sk + e) modq$$

$$pk_2 = a$$

where $a$ is randomly chosen from $R_q$ and $e$ is a random error from an error distribution $\chi$.

Encryption & Decryption

In order to encrypt a plaintext message $m \in P$, we first generate three small random polynomials $u \in R_2$, $e_1, e_2 \in \chi$ and return a ciphertext $c = (c_1, c_2) \in C$ as follows:

$$c_1 = pk_1 \cdot u + e_1 + \Delta m modq$$

$$c_2 = pk_2 \cdot u + e_2 modq$$

where $\Delta = \lfloor \frac{q}{t} \rfloor$.

Decryption is performed by evaluating the ciphertext on the secret key as follows and inverting the scaling factor applied in encryption:

$$ m = \lfloor \frac{t(c_1 + c_2 \cdot sk) mod q}{q} \rfloor mod t $$

Homomorphic Computations

Addition

$$ Add(c^{(1)}, c^{(2)}) = (c_1^{(1)} + c_1^{(2)} mod q, c_2^{(1)} + c_2^{(2)} mod q) $$

$$ = (c_1^{(3)}, c_2^{(3)}) = c^{(3)} $$

To understand why this works, let's break down the process: Assume that $c^{(1)}$ and $c^{(2)}$ are fresh encryptions of $m^{(1)}$ and $m^{(2)}$. Algebraically, they can be expressed as follows:

$$ C^{(1)} = \left(pk_1 \cdot u^{(1)} + t \cdot e^{(1)}_1 + m^{(1)} \mod q, \ pk_2 \cdot u^{(1)} + t \cdot e^{(1)}_2 \mod q\right) $$

$$ C^{(2)} = \left(pk_1 \cdot u^{(2)} + t \cdot e^{(2)}_1 + m^{(2)} \mod q, \ pk_2 \cdot u^{(2)} + t \cdot e^{(2)}_2 \mod q\right) $$

By substituting $c^{(1)}$ and $c^{(2)}$ into the homomorphic addition formula, we get:

$$ c^{(3)} = (c^{(3)}_1, c^{(3)}_2)  $$

$$ = \left(pk_1 \cdot (u^{(1)} + u^{(2)}) + t \cdot (e^{(1)}_1 + e^{(2)}_1) + (m^{(1)} + m^{(2)}) \mod q, \ pk_2 \cdot (u^{(1)} + u^{(2)}) + t \cdot (e^{(1)}_2 + e^{(2)}_2) \mod q\right) $$

It is clear that this represents a valid ciphertext encrypting $m^{(3)} = m^{(1)} + m^{(2)}$. The error term in $c^{(3)}$ is approximately the sum of the noise terms in the input ciphertexts, meaning the noise grows additively.

Multiplication

Multiplying two ciphertexts gives us

$$ c^{(1)} \cdot c^{(2)} = \Delta^2 m^{(1)} \cdot m^{(2)} + \Delta (m^{(1)} \cdot v_2 + m^{(2)} \cdot v_1)) + q (v_1 \cdot r_2 + v_2 \cdot r_1) + q \cdot \Delta (m^{(1)} \cdot r_2 + m^{(2)} \cdot r_1) + v_1 \cdot v_2 + q^2 \cdot r_1 \cdot r_2 $$

Notice that the term $ q^2 \cdot r_1 \cdot r_2 $ produces large noise since $ q^2 $ doesn’t divide $ \Delta $. This is the reason why we scale by the scaling factor $ t/q $.

Now, we can write

$$m^{(1)} \cdot m^{(2)} = (m^{(1)} \cdot m^{(2)} modt)t \cdot r_m$$

and

$$ v_1 \cdot v_2 = (v_1 \cdot v_2 mod \Delta) + \Delta \cdot r_v $$

Now, expansion gives us the verification. Consider the product of two ciphertexts scaled by $\frac{t}{q}$:

$$ \frac{t}{q}(C^{(1)} \cdot c^{(2)})(sk) = \Delta (m^{(1)} \cdot m^{(2)} \mod t) + (m^{(1)} \cdot v_2 + m^{(2)} \cdot v_1) + t (v_1 \cdot r_2 + v_2 \cdot r_1) + r_v + (q - (q \mod t)) \cdot (r_m + m^{(1)} \cdot r_2 + m^{(2)} \cdot r_1) + \frac{t}{q} (v_1 \cdot v_2 \mod \Delta) $$

The final step in the derivation involves reducing this expression modulo $q$, which gives us:

$$ \frac{t}{q}(c^{(1)} \cdot c^{(2)})(sk) = \Delta (m^{(1)} \cdot m^{(2)} \mod t) + (m^{(1)} \cdot v_2 + m^{(2)} \cdot v_1) + t (v_1 \cdot r_2 + v_2 \cdot r_1) + r_v - (q \mod t) (r_m + m^{(1)} \cdot r_2 + m^{(2)} \cdot r_1) + r_e $$

where $r_e$ is the rounding error generated from the last two terms in the equation.

Relinearization

The primary goal of relinearization is to reduce the size of product ciphertexts, which result from `Mul`, back to two ring elements. To address this, we define $ C^* = \{C^*_1, C^*_2, C^*_3\} $. Our objective is to find $ \hat{C}^* = \{\hat{C}^*_1, \hat{C}^*_2\} $ such that:

$$ (C^*_1 + C^*_2 \cdot SK + C^*_3 \cdot SK^2 \mod q) \approx (\hat{C}^*_1 + \hat{C}^*_2 \cdot SK + r \mod q) $$

The evaluation key $ EK = (-(a \cdot SK + e) + SK^2, a) $ allows access to $ SK^2 $. This key is a masked version of $ SK^2 $ because $ EK_1 + EK_2 \cdot SK = SK^2 - e $. Using this, we can compute $ \hat{C}^* $ as follows:

$$ \hat{C}^*_1 = (C^*_1 + EK_1 \cdot C^*_3 \mod q) $$

$$ \hat{C}^*_2 = (C^*_2 + EK_2 \cdot C^*_3 \mod q) $$

To decrypt this equation, we get:

$$ \hat{C}^*_1 + \hat{C}^*_2 \cdot SK = C^*_1 + EK_1 \cdot C^*_3 + SK \cdot (C^*_2 + EK_2 \cdot C^*_3) $$

$$ = C^*_1 + C^*_2 \cdot SK + C^*_3 \cdot (EK_1 + EK_2 \cdot SK) = C^*_1 + C^*_2 \cdot SK + C^*_3 \cdot SK^2 + C^*_3 \cdot e $$

It is important to note that the term $ C^*_3 \cdot e $ can be quite large since $ C^*_3 $ has coefficients in $ \mathbb{Z}_q $.

Conclusion

The BFV (Brakerski/Fan-Vercauteren) encryption scheme brings significant advancements in the field of fully homomorphic encryption. 

BFV and BGV share many foundational elements but differ in their specific implementations and optimizations. BFV, built on the RLWE problem, focuses on efficient operations over polynomial rings, enabling practical encrypted computations. BGV extends this by introducing techniques like Modulus Switching to better control noise growth during homomorphic operations.

In summary, this encryption scheme allow for secure and efficient data processing, pushing the boundaries of what is possible with encrypted computations.