Fully Homomorphic Encryption (FHE) represents one of the most significant achievements in modern cryptography, enabling computation on encrypted data without decryption. This post provides a comprehensive technical analysis of three dominant FHE schemes: BGV (Brakerski-Gentry-Vaikuntanathan), BFV (Brakerski-Fan-Vercauteren), and CKKS (Cheon-Kim-Kim-Song). We’ll explore their mathematical foundations using consistent notation and compare their approaches to critical challenges in homomorphic computation.

Mathematical Notations and Concepts

We use the following consistent notation to describe the BGV, BFV, and CKKS schemes.

Core Mathematical Structures

Symbol	Definition
$\mathbb{Z}, \mathbb{R}, \mathbb{C}$	Integers, Real numbers, and Complex numbers
$\mathbb{Z}_q$	Integers modulo $q$, i.e., $\{0, \dots, q-1\}$
$R_q$	Polynomial ring $\mathbb{Z}_q[X]/(X^N + 1)$ (degree $<N$, coeff. mod $q$)
$N$	Polynomial degree (power of 2, e.g., $2^{11}$ to $2^{15}$)
$\leftarrow$	Sampling from a distribution (e.g., $e \leftarrow \chi$)
$\lfloor \cdot \rceil, \lfloor \cdot \rfloor$	Rounding to nearest integer, Floor function
$\|\|\cdot\|\|_\infty$	Infinity norm (maximum absolute value of coefficients)

Cryptographic Variables & Operations

Symbol	Meaning	Notes
$s$	Secret key	Polynomial in $R$ (often small/binary)
$pk, evk$	Public key, Evaluation key	$pk=(pk_0, pk_1)$, $evk$ used for relinearization
$ct$	Ciphertext	Pair of polynomials $(c_0, c_1) \in R_q^2$
$m$	Plaintext message	Encoded data as a polynomial
$e, \chi$	Error, Error dist.	Small noise drawn from Discrete Gaussian $\chi$
$u$	Ephemeral key	Small random polynomial used in encryption
$[\cdot]_q$	Modulo reduction	Coefficient-wise reduction into $[0, q-1]$

Scheme Parameters

Symbol	Description	Context
$q, t$	Ciphertext / Plaintext modulus	$q$ is large, $t$ is small (BGV/BFV)
$\Delta$	Scaling factor	$\lfloor q/t \rfloor$ (BFV) or precision scale (CKKS)
$L$	Multiplicative depth	Number of levels allowed in the circuit
$w, P$	Relinearization bases	Base $w$ or large factor $P$ for key switching
$\vec{z}$	Complex vector	Input data vector for CKKS $\in \mathbb{C}^{N/2}$
$\sigma, \lambda$	Noise std. dev, Security param	typically $\lambda=128$ bits

The Foundation: Ring Learning With Errors (RLWE)

All three schemes build upon the Ring Learning With Errors (RLWE) problem, which provides their cryptographic security. Let’s establish our common notation:

• $R = \mathbb{Z}[X]/(X^N + 1)$ where $N$ is a power of 2 (typically 2048, 4096, or 8192)
• $R_q = R/qR = \mathbb{Z}_q[X]/(X^N + 1)$ for modulus $q$
• $R_t = R/tR = \mathbb{Z}_t[X]/(X^N + 1)$ for plaintext modulus $t$
• $\chi$ denotes the error distribution (typically discrete Gaussian)

The RLWE problem asks: given many pairs $(a_i, b_i = a_i \cdot s + e_i) \in R_q^2$ where $s \in R_q$ is secret and $e_i \leftarrow \chi$, it is computationally hard to recover $s$.

Common Framework

Despite their differences, BGV, BFV, and CKKS share a common structure. Let’s define the core operations using unified notation:

Key Generation

All three schemes generate keys similarly:

Secret Key Generation: $s \leftarrow \chi \text{ or } s \leftarrow R_2 \text{ (binary secret)}$

Public Key Generation: $pk = (pk_0, pk_1) = ([-a \cdot s + e]_q, a)$ where $a \leftarrow R_q$ uniformly random and $e \leftarrow \chi$.

Evaluation Key Generation (for relinearization): $evk = (evk_0, evk_1) = ([-a \cdot s + e + P \cdot s^2]_{P \cdot q}, a)$ where $P$ is a large integer used for key switching.

Basic Ciphertext Structure

A fresh ciphertext encrypting message $m$ has the form: $ct = (c_0, c_1) \in R_q^2$

The invariant maintained is: $c_0 + c_1 \cdot s = m + e \pmod{q}$ where $e$ is small noise.

Message Encoding and SIMD Batching

A crucial aspect of modern FHE implementation is SIMD (Single Instruction, Multiple Data) packing. Instead of encrypting a single number into a massive polynomial (which is inefficient), we “pack” a vector of messages into a single polynomial.

BGV and BFV: Integer Batching (CRT Packing)

For BGV and BFV, the plaintext space is the ring $R_t = \mathbb{Z}_t[X]/(X^N + 1)$. If we choose the plaintext modulus $t$ to be a prime such that $t \equiv 1 \pmod{2N}$, the polynomial $X^N + 1$ factors completely into linear terms $(X - \zeta_i)$ in $\mathbb{Z}_t$.

By the Chinese Remainder Theorem (CRT), there is an isomorphism: $R_t \cong \mathbb{Z}_t \times \mathbb{Z}_t \times ... \times \mathbb{Z}_t \quad (N \text{ slots})$

Encoding: Given a vector of integers $\vec{m} = (m_0, m_1, ..., m_{N-1}) \in \mathbb{Z}_t^N$, we construct a unique polynomial $m(X) \in R_t$ such that: $m(\zeta_i) = m_i \pmod t$ This is efficiently computed using a Number Theoretic Transform (NTT).

Decoding: Evaluate the decrypted polynomial $m(X)$ at the roots $\zeta_i$ to recover the vector $\vec{m}$.

Homomorphic SIMD: Addition/Multiplication of polynomials $m_A(X) \cdot m_B(X)$ corresponds to component-wise operations on the vectors: $\vec{m}_A \odot \vec{m}_B$.

CKKS: Complex Batching (Canonical Embedding)

CKKS works with vectors of complex numbers $\mathbb{C}^{N/2}$. It utilizes the Canonical Embedding $\sigma: R \rightarrow \mathbb{C}^N$.

Encoding: Given a vector $\vec{z} \in \mathbb{C}^{N/2}$:

1. Expand to a conjugate-symmetric vector in $\mathbb{C}^N$.
2. Apply the inverse Canonical Embedding (essentially an inverse FFT) to map the vector to a polynomial with real coefficients.
3. Scale the coefficients by $\Delta$ and round to the nearest integers to get $m(X) \in R$.

Decoding:

1. Scale down the coefficients of the decrypted polynomial by $\Delta$.
2. Apply the Canonical Embedding (FFT) to recover the vector of values.

This mapping allows performing approximate arithmetic on $N/2$ complex slots simultaneously.

BGV: Encoding in Least Significant Bits

The BGV scheme encodes messages in the least significant bits of ciphertext coefficients, employing modulus switching to manage noise growth.

BGV Encryption

Given plaintext $m \in R_t$:

1. Sample $u \leftarrow R_2$ (small polynomial)
2. Sample $e_0, e_1 \leftarrow \chi$
3. Compute: $c_0 = pk_0 \cdot u + e_0 + m$ $c_1 = pk_1 \cdot u + e_1$
4. Return $ct = (c_0, c_1) \in R_q^2$

BGV Decryption

$m' = [c_0 + c_1 \cdot s]_q \bmod t$

The decryption is correct if the noise $||c_0 + c_1 \cdot s - m||_\infty < q/(2t)$.

BGV Homomorphic Operations

Addition: $ct_{add} = ct_1 + ct_2 = (c_0^{(1)} + c_0^{(2)}, c_1^{(1)} + c_1^{(2)})$

Multiplication:

1. Compute tensor product: $ct_{mult}' = (d_0, d_1, d_2)$ where:

   • $d_0 = c_0^{(1)} \cdot c_0^{(2)}$
   • $d_1 = c_0^{(1)} \cdot c_1^{(2)} + c_1^{(1)} \cdot c_0^{(2)}$
   • $d_2 = c_1^{(1)} \cdot c_1^{(2)}$

2. Relinearization reduces back to degree 2 (covered below)

BGV Modulus Switching

After operations, reduce modulus from $q$ to $q' = q/p$: $c_i' = \lfloor \frac{q'}{q} \cdot c_i \rceil$

This scales down both the ciphertext and noise proportionally.

BFV: Encoding in Most Significant Bits

BFV encodes messages in the most significant bits, using a different multiplication strategy.

BFV Encryption

Given plaintext $m \in R_t$:

1. Sample $u \leftarrow R_3$ (ternary polynomial)
2. Sample $e_0, e_1 \leftarrow \chi$
3. Compute: $c_0 = pk_0 \cdot u + e_0 + \Delta \cdot m$ $c_1 = pk_1 \cdot u + e_1$ where $\Delta = \lfloor q/t \rfloor$
4. Return $ct = (c_0, c_1) \in R_q^2$

BFV Decryption

$m' = \lfloor \frac{t}{q} \cdot [c_0 + c_1 \cdot s]_q \rceil \bmod t$

BFV Homomorphic Operations

Addition: Same as BGV

Multiplication:

1. Compute intermediate values in $\mathbb{Z}[X]/(X^N + 1)$ (without mod $q$): $\tilde{c}_0 = c_0^{(1)} \cdot c_0^{(2)}$ $\tilde{c}_1 = c_0^{(1)} \cdot c_1^{(2)} + c_1^{(1)} \cdot c_0^{(2)}$ $\tilde{c}_2 = c_1^{(1)} \cdot c_1^{(2)}$

2. Scale and round: $c_i = \lfloor \frac{t}{q} \cdot \tilde{c}_i \rceil \bmod q$

3. Apply relinearization to reduce from 3 to 2 components

CKKS: Approximate Arithmetic for Real Numbers

CKKS fundamentally differs by supporting approximate arithmetic on complex/real numbers.

CKKS Encoding

CKKS uses a special encoding that maps vectors of complex numbers to polynomials:

$\text{Encode}: \mathbb{C}^{N/2} \rightarrow R$ $\vec{z} = (z_0, z_1, ..., z_{N/2-1}) \mapsto m(X)$

This uses the canonical embedding via primitive $N$-th roots of unity.

CKKS Encryption

Given encoded message $m \in R$ at scale $\Delta$:

1. Sample $u \leftarrow R_3$
2. Sample $e_0, e_1 \leftarrow \chi$
3. Compute: $c_0 = pk_0 \cdot u + e_0 + m$ $c_1 = pk_1 \cdot u + e_1$
4. Return $ct = (c_0, c_1) \in R_{q_L}^2$ at level $L$

CKKS Decryption and Decoding

1. Decrypt: $m' = c_0 + c_1 \cdot s \bmod q_L$
2. Decode: $\vec{z}' = \text{Decode}(m'/\Delta)$

The result $\vec{z}'$ approximates the original vector within some error bound.

CKKS Homomorphic Operations

Addition: Standard component-wise addition (same scale required)

Multiplication:

1. Multiply as in BGV/BFV to get $(d_0, d_1, d_2)$
2. Relinearize to $(c_0', c_1')$
3. Rescale (unique to CKKS): $c_i'' = \lfloor c_i'/p \rceil$ where $p$ is a prime in the modulus chain

The rescaling step is crucial: it reduces both the scale (from $\Delta^2$ to $\Delta$) and the modulus (from $q_L$ to $q_{L-1} = q_L/p$).

Relinearization: Converting Degree-3 to Degree-2 Ciphertexts

After multiplication, all schemes produce degree-3 ciphertexts that must be reduced:

Key Switching Technique

Given $(d_0, d_1, d_2)$ where the invariant is $d_0 + d_1 \cdot s + d_2 \cdot s^2 = m \cdot m' + e$:

1. Decompose $d_2$ into base-$w$ digits: $d_2 = \sum_{i=0}^{k-1} d_{2,i} \cdot w^i$

2. Use evaluation key components: $c_0' = d_0 + \sum_{i=0}^{k-1} d_{2,i} \cdot evk_{0,i}$ $c_1' = d_1 + \sum_{i=0}^{k-1} d_{2,i} \cdot evk_{1,i}$

The result $(c_0', c_1')$ maintains the same message but with slightly increased noise.

Noise Management Strategies

The three schemes employ distinct approaches to noise management:

BGV: Modulus Switching

• Actively reduces noise after each level
• Maintains constant noise magnitude
• Requires careful parameter ladder: $q_L > q_{L-1} > ... > q_0$

BFV: Scale-Invariant Approach

• Keeps modulus $q$ fixed throughout computation
• Noise grows but remains manageable through careful analysis
• Simpler parameter selection than BGV

CKKS: Rescaling

• Naturally reduces noise through rescaling after multiplication
• Trades precision for noise reduction
• Allows deeper circuits than exact schemes for approximate computation

Parameter Selection

Key parameters affect security, correctness, and performance:

Common Parameters

• Polynomial degree $N$: Higher values increase security and capacity but slow operations
• Modulus bit-length: Balances security and noise budget
• Standard deviation $\sigma$ of error distribution: Affects security and correctness

Scheme-Specific Considerations

BGV:

• Modulus chain: $q_L = \prod_{i=0}^L p_i$ where each $p_i \approx 2^{40-60}$
• Typically requires $L =$ depth of circuit

BFV:

• Single large modulus: $q \approx 2^{109-880}$ depending on $N$ and depth
• Plaintext modulus $t$ often prime for better noise tolerance

CKKS:

• Scale $\Delta \approx 2^{40}$ for good precision
• Special primes for rescaling in modulus chain
• Can handle deeper circuits due to approximate nature

Practical Performance Comparison

Computational Efficiency

• Addition: All schemes have similar performance ($O(N)$ operations)
• Multiplication: BFV slightly slower due to scaling step; CKKS benefits from rescaling
• Bootstrapping: BGV/BFV require complex exact bootstrapping; CKKS has simpler approximate bootstrapping

Use Case Suitability

BGV: Best for:

• Integer arithmetic with known depth
• Applications requiring exact computation
• Scenarios where modulus switching overhead is acceptable

BFV: Best for:

• Integer arithmetic with simpler parameter selection
• Batched operations on binary or small integer data
• Applications where fixed modulus simplifies implementation

CKKS: Best for:

• Machine learning and statistical computations
• Signal processing and scientific computing
• Deep circuits where approximation is acceptable

Security Considerations

All three schemes base security on RLWE hardness, but parameters must be chosen carefully:

$\text{Security level} \approx \frac{N \cdot \log q}{\sigma^2}$

Current recommendations (128-bit security):

• $N = 2^{14}, \log q \approx 438$ bits
• $N = 2^{13}, \log q \approx 218$ bits
• $N = 2^{12}, \log q \approx 109$ bits

Implementation Considerations

Library Support

Popular libraries implement these schemes with optimizations:

• SEAL (Microsoft): BFV and CKKS
• HElib (IBM): BGV and CKKS
• PALISADE/OpenFHE: All three schemes
• TenSEAL: Python wrapper focusing on CKKS for ML

Optimization Techniques

1. NTT/FFT acceleration: Polynomial multiplication in $O(N \log N)$
2. RNS representation: For large moduli in BGV/BFV
3. Batching: SIMD operations on packed plaintexts
4. Key compression: Reduce evaluation key size

Future Directions

Recent research (2024-2025) focuses on:

• Bootstrapping improvements: Faster refresh procedures
• Compiler tools: Automatic parameter selection and circuit optimization
• Hardware acceleration: FPGA/ASIC implementations
• Standardization: Homomorphic Encryption Standard ongoing work

Conclusion

BGV, BFV, and CKKS each offer unique advantages for different homomorphic encryption applications. BGV provides fine-grained noise control through modulus switching, BFV simplifies implementation with fixed modulus, and CKKS enables efficient approximate arithmetic for real-world numerical computations. Understanding their mathematical foundations and trade-offs is crucial for selecting the appropriate scheme for specific applications.

The consistent mathematical framework presented here demonstrates that despite surface-level differences, these schemes share fundamental principles rooted in RLWE hardness. As FHE continues to mature, we can expect further optimizations and potentially new schemes that combine the best features of existing approaches.

References and Further Reading

For those interested in diving deeper into the mathematical foundations and recent developments:

• Leveled Homomorphic Encryption Schemes for Homomorphic Encryption Standard (2024)
• BGV: Comprehensive Technical Overview
• Finding and Evaluating Parameters for BGV
• A High-Level Technical Overview of Fully Homomorphic Encryption
• Homomorphic Encryption Standard