Part 5: BGV Scheme | Building Blocks of FHE

The BGV scheme is recognized as part of the second generation of FHE schemes, built upon the Ring Learning with Errors (RLWE) problem. BGV operates over two distinct rings: the plaintext ring and the ciphertext ring. Like other FHE schemes, BGV enables an untrusted party to perform meaningful computations on encrypted data without requiring access to the decryption key.

Fundamentals

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 and Ciphertext Spaces

The plaintext and ciphertext spaces in BGV are similar to those in BFV. The plaintext polynomial ring is defined as $\mathcal{P} = R_t = \mathbb{Z}_t[x]/(x^n + 1)$, which means it consists of polynomials with degrees less than $n$ and coefficients in $\mathbb{Z}_t$, where both the plaintext modulus $t$ and the ring dimension $n$ are integers. The ciphertext space is given by $\mathcal{C} = R_{q_l} \times R_{q_l}$, where $R_{q_l} = \mathbb{Z}_{q_l}[x]/(x^n + 1)$ and $q_l \in \mathbb{Z}$ represents the ciphertext modulus at level $l$.

For practical reasons, $n$ is usually set as a power-of-2 integer, similar to what is done in BFV. Additionally, $q$ is typically much larger than $t$, affecting the expansion rate of the message after encryption. It is important to consider the security and functionality constraints associated with these parameters.

Key Generation

The secret key $sk$ is a random ternary polynomial generated from $R_2$. The public key $pk$ consists of a pair of polynomials $(pk_1, pk_2)$, which are calculated as follows:

$$ pk_1 = (-1 \cdot (a \cdot sk + t \cdot e) \mod q_l)  $$

$$ pk_2 = a $$

Here, $a$ is a random polynomial in $R_{q_l}$, and $e$ is a random error polynomial sampled from $\chi$. The notation $\mod q_l$ indicates that the polynomial arithmetic is performed modulo $q_l$. Note that the error is scaled by $t$ here, unlike in the key generation process for BFV.

Encryption and Decryption

The encryption algorithm takes a plaintext message $M$ in $\mathcal{P}$ and the public key $pk$, and outputs the ciphertext $C = (C_1, C_2)$, effectively encrypting the message. The encryption process involves generating three small random polynomials from $R_2$ and $e_1$ and $e_2$ from $\chi$, and then computing:

$ C_1 = (pk_1 \cdot u + t \cdot e_1 + M \mod q_l) $

$ C_2 = (pk_2 \cdot u + t \cdot e_2 \mod q_l) $

Notice how the error polynomial in $C_1$ is scaled by the plaintext modulus $t$. This aligns with the earlier demonstration, where the message occupies the lower bits of the ciphertext coefficient while the noise can grow in the upper bits.

The decryption process reverses encryption by taking the ciphertext and the secret key $sk$ as input. It retrieves the plaintext message $M$, assuming the noise remains manageable throughout computation. Decryption proceeds as follows:

$$ M = \left( (C_1 + C_2 \cdot sk \mod q_l) \mod t \right) $$

To understand why decryption works and under what conditions, let's expand Equation (3) assuming that decryption happens immediately after encryption for simplicity:

$$ C_1 + C_2 \cdot sk = pk_1 \cdot u + t \cdot e_1 + M + (pk_2 \cdot u + t \cdot e_2) \cdot sk $$

$$ = \left( - (a \cdot sk + t \cdot e) \cdot u + t \cdot e_1 + M + a \cdot u \cdot sk + t \cdot e_2 \cdot sk \right) \mod q_l $$

$$ = M - t \cdot e \cdot u + t \cdot e_1 + t \cdot e_2 \cdot sk \mod q_l $$

$$ = M + t \cdot v $$

By reducing the result modulo $t$, we eliminate the noise vector $v$ and retrieve $M$ without the noise. However, this process is contingent on the norm of $v$ being small enough, specifically $||v||_\infty < \frac{q_l}{2t}$, where $||v||_\infty$ is the largest absolute coefficient in $v$. The bound ensures that the noise magnitude does not grow excessively and distort the message.

Homomorphic Evaluation

Addition

Homomorphic addition combines two ciphertexts $C^{(1)}$ and $C^{(2)}$, defined with respect to the same modulus $q_l$, and produces a new ciphertext $C^{(3)}$ that encrypts the sum of the two plaintext messages. Specifically, the decryption of $C^{(3)}$ using the secret key $sk$ yields $M^{(1)} + M^{(2)} \mod t$, provided the error in the resulting ciphertext is within acceptable bounds. This process involves simply adding the corresponding polynomials in each ciphertext.

$$ \text{Add}(C^{(1)}, C^{(2)}) = \left((C^{(1)}_1 + C^{(2)}_1 \mod q_l), (C^{(1)}_2 + C^{(2)}_2 \mod q_l)\right) = (C^{(3)}_1, C^{(3)}_2) = C^{(3)} $$

To understand why this works, let's break down the homomorphic addition by assuming $C^{(1)}$ and $C^{(2)}$ are fresh encryptions of $M^{(1)}$ and $M^{(2)}$. These can be expressed as follows:

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

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

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

$$ 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_l, \ pk_2 \cdot (u^{(1)} + u^{(2)}) + t \cdot (e^{(1)}_2 + e^{(2)}_2) \mod q_l\right) $$

It is evident that this represents a valid ciphertext encrypting $M^{(3)} = M^{(1)} + M^{(2)}$. Note that the error term in $C^{(3)}$ is the sum of the noise terms in the input ciphertexts, meaning the noise grows additively.

Multiplication

Homomorphic multiplication combines two ciphertexts $C^{(1)}$ and $C^{(2)}$, defined with respect to the same modulus $q_l$, and produces a ciphertext $C^{(3)}$ that encrypts the product of the two plaintext messages. Specifically, the decryption of $C^{(3)}$ using the secret key $sk$ yields $M^{(1)} \cdot M^{(2)} \mod t$. 

In the following analysis, we interpret the decryption formula as a ciphertext evaluation at $sk$:

$$ C^{(1)}(sk) = M^{(1)} + t \cdot v_1 + q_l \cdot r_1 $$

$$ C^{(2)}(sk) = M^{(2)} + t \cdot v_2 + q_l \cdot r_2 $$

Multiplying the ciphertexts gives us:

$$ (C^{(1)} \cdot C^{(2)})(sk) = M^{(1)} \cdot M^{(2)} + t (M^{(1)} \cdot v_2 + M^{(2)} \cdot v_1) + q_l (v_1 \cdot r_2 + v_2 \cdot r_1) + q_l (M^{(1)} \cdot r_2 + M^{(2)} \cdot r_1) + t^2 \cdot v_1 \cdot v_2 + q_l^2 \cdot r_1 \cdot r_2 $$

$$ = M^{(1)} \cdot M^{(2)} + t (M^{(1)} \cdot v_2 + M^{(2)} \cdot v_1) + t \cdot v_1 \cdot v_2 $$

The decryption formula of the product ciphertext has the structure of a valid ciphertext encrypting $M^{(1)} \cdot M^{(2)}$ with noise $v = M^{(1)} \cdot v_2 + M^{(2)} \cdot v_1 + t \cdot v_1 \cdot v_2$. Note how the noise term grows multiplicatively as the product of the noise in the input ciphertexts (the term $t \cdot v_1 \cdot v_2$). This means that as we go deeper in the computation, the noise grows exponentially. To resolve this problem, BGV uses ModSwitch to reduce the rate at which multiplication noise grows. ModSwitch will be described later on in this article.

From the above discussion, we can deduce that Mul can be evaluated as polynomial multiplication of the input ciphertexts, as shown in the following equation:

$$ \text{Mul}(C^{(1)}, C^{(2)}) = \left(\left(\left(C^{(1)}_1 \cdot C^{(2)}_1 \right) \mod q_l, \left(C^{(1)}_1 \cdot C^{(2)}_2 + C^{(1)}_2 \cdot C^{(2)}_1 \right) \mod q_l, \left(C^{(1)}_2 \cdot C^{(2)}_2 \right) \mod q_l\right)\right) $$

Mul increases the number of ring elements in the resulting ciphertext from 2 to 3. Moreover, the product ciphertext is defined with respect to $sk^2$ rather than the original $sk$, making it decryptable using $sk^2$. In order to reduce the number of elements back to 2 and make the ciphertext decryptable using $sk$, the Relinearization procedure, described next, can be used.

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 $.

Modulus Switching

ModSwitch is a technique used to manage the noise generated during multiplication operations. This concept was first introduced in [BGV14]. It utilizes the idea that a ciphertext $C$ defined with respect to modulus $q$ and secret key $sk$ can be transformed into an equivalent ciphertext $C'$ defined with respect to another modulus $q'$ while maintaining the same secret key $sk$ such that:

$$ (C(sk) \mod q) = (C'(sk) \mod q') $$

The transformation is accomplished by scaling the coefficients of $C$ by the factor $q'/q$ and then applying appropriate rounding. To effectively reduce the noise magnitude, a smaller $q'$ is selected compared to $q$, allowing us to scale down the multiplication noise.

In the context of BGV, $q$ can be at any level $l$, that is, $q_l$, and $q'$ in this context is simply $q_{l-1}$. The ciphertext moduli $q_l$ for $0 \le l \le L$ are chosen such that they are equivalent modulo $t$. This results in scaling down the noise without affecting the encrypted plaintext message. Essentially, it is akin to scaling by 1 from the plaintext perspective.

ModSwitch can be computed as shown in the following equation, where $[\cdot]$ denotes a suitable rounding function. The transformed ciphertext $C'$ is defined with respect to the new modulus $q'$:

$$ C' = \left[\frac{q'}{q} \cdot C \right] $$

Conclusion

The BGV (Brakerski-Gentry-Vaikuntanathan) encryption scheme brings significant advancements in the field of fully homomorphic encryption. BGV and BFV share many foundational elements but differ in their specific implementations and optimizations. BGV, built on the RLWE problem, introduces techniques like Modulus Switching to efficiently manage noise growth during homomorphic operations, enabling practical encrypted computations. BFV focuses on polynomial ring efficiency, while BGV emphasizes noise control to facilitate deeper computation. In summary, this encryption scheme allows for secure and efficient data processing, pushing the boundaries of what is possible with encrypted computations.