Generalized BFV in Practice

Fully homomorphic encryption (FHE) promises to unlock computation on encrypted data, but practical schemes face fundamental limitations that constrain their real-world applicability. The BFV (Brakerski-Fan-Vercauteren) scheme, one of the most widely used FHE constructions, exemplifies a critical trade-off that has shaped the field: you can either pack large amounts of data per ciphertext or perform deep computations, but not both.

This limitation isn't merely a technical inconvenience, it fundamentally constrains the types of applications FHE can serve. Machine learning inference on encrypted data, secure database queries, and privacy-preserving analytics all demand both high data throughput and substantial computational depth. Yet classical BFV forces practitioners into an uncomfortable choice between these requirements.

Recent advances in generalized BFV schemes offer a path beyond this trade-off. By replacing the traditional integer plaintext modulus with carefully chosen polynomial quotients, these constructions can maintain large plaintext spaces while achieving multiplicative depths that scale with the ciphertext modulus rather than being inversely related to the plaintext size.

This article explores how the quotient-by-$t(X) = X^k - b$ construction breaks free from classical BFV's fundamental limitations, examining both the mathematical foundations and practical implications of this approach.

Classical BFV: The Foundation

Let $N = 2^{n}$ be the cyclotomic index. The classical BFV scheme operates over:

• Ciphertext ring: $R_{q} = \mathbb{Z}_{q}[X]/(X^{N}+1)$
• Plaintext modulus: an integer $t\ll q$
• Scaling factor: $\Delta = \lfloor q/t \rfloor \simeq q/t$
• Secret/error: $s \leftarrow R_{2}$ and $e \leftarrow \chi$
• Centered reduction: $\lfloor x \rceil_{t} \in (-t/2,t/2]$

The core operations follow a familiar pattern:

KeyGen: Pick $a \leftarrow R_{q}$, $s \leftarrow R_{2}$, $e \leftarrow \chi$; set $b = -(as + e) \in R_{q}$. Public key $(b, a)$; secret key $s$.

Encrypt $m \in \mathbb{Z}_{t}[X]/(X^{N}+1)$:

$$\mathrm{ct}=\,\bigl([\Delta m + as + e]_{q},\; -a\bigr)\in R_{q}^{2}$$

Decrypt $\mathrm{ct}=(c_{0},c_{1})$:

$$m = \Bigl\lfloor \frac{c_{0}+c_{1}s}{\Delta} \Bigr\rceil_{t}$$

The Fundamental Bottleneck

The core limitation of classical BFV stems from its noise growth behavior. Increasing the plaintext modulus $t$ to pack more data per ciphertext comes at a steep cost: the maximum multiplicative depth is roughly bounded by $\log q / \log t$, so larger plaintext spaces directly reduce computational capacity. To maintain depth while increasing $t$, we must grow $q$ proportionally, but larger ciphertext moduli make every operation more expensive: more memory for keys, slower NTTs for polynomial arithmetic, and costlier key-switching.

The result is an unavoidable choice: high-throughput applications with large $t$ sacrifice multiplicative depth, while deep computations are constrained to small plaintext spaces.

For the foundational BFV construction and security analysis, see "Somewhat Practical Fully Homomorphic Encryption"

The Key Breakthrough: Generalized BFV

The breakthrough comes from recognizing that the plaintext modulus need not be an integer. Instead of working modulo $t \in \mathbb{Z}$, we can construct plaintext rings using polynomial quotients of the form $t(X) = X^k - b$, where $b$ is a small integer and $k$ divides certain structural parameters of the cyclotomic polynomial.

This seemingly simple change has profound implications for noise growth and multiplicative depth, offering a path to escape classical BFV's fundamental limitations.

The Mathematical Setup

We keep the ciphertext ring exactly as in classical BFV, using one NTT-friendly prime:

$$R_q = \mathbb{Z}_q[X]\big/(X^{N}+1), \qquad q\equiv1\pmod{2N}$$

For the plaintext ring, we introduce a binomial relation. Write $m=2N$ and let:

• $r=\operatorname{rad}(m)$ - the radical of $m$ (product of distinct primes dividing $m$)
• $k\mid (m/r)$ - our chosen binomial degree
• $t(X)=X^{k}-b$ with a small base $|b|\ll q$

Constructing the New Plaintext Space

We leverage a classical identity for cyclotomic polynomials:

$$\Phi_{m}(X)=\Phi_{r}\bigl(X^{\,m/r}\bigr)$$

Proof

Notation and basic definitions

$\mathrm{rad}(n) := \prod_{p \mid n} p$ (the product of distinct primes dividing $n$); equivalently $\mathrm{rad}(n)$ is the largest square-free divisor of $n$.

Euler’s totient $\varphi(n) = |\{1 \le k \le n : \gcd(k,n) = 1\}|$.

Möbius function $\mu(1)=1$; $\mu(n)=0$ if $n$ is divisible by a square; $\mu(n)=(-1)^r$ if $n$ is a product of $r$ distinct primes.

$n$-th cyclotomic polynomial $\displaystyle \Phi_n(X) := \prod_{1 \le k \le n \ \gcd(k,n)=1}\bigl(X - e^{2\pi i k/n}\bigr)$ the unique monic polynomial whose roots are the primitive $n$-th roots of unity. It has degree $\varphi(n)$ and integer coefficients.

Theorems used in the proof

Theorem  If arithmetic functions $f,g$ satisfy $f(n) = \prod_{d\mid n} g(d)\quad\text{for every }n\ge1,$ then $g(n) = \sum_{d\mid n} f\bigl(n/d\bigr)^{\mu(d)}.$

Proof. Assume $f(n)=\prod_{d\mid n} g(d)$. Consider $P := \prod_{d\mid n} f(n/d)^{\mu(d)}.$ Insert the definition of $f$: $P = \prod_{d\mid n} \Bigl(\prod_{e\mid n/d} g(e)\Bigr)^{\mu(d)}.$ Re-index: each pair $(d,e)$ with $de\mid n$ appears once; write $n=de\cdot m$ with $m=1$. $P = \prod_{e\mid n} g(e)^{\sum_{d\mid n/e}\mu(d)}.$ But $\sum_{d\mid m}\mu(d)=0$ for $m>1$ and $=1$ for $m=1$. Hence all exponents vanish except when $e=n$, giving $P=g(n)$.

Theorem  For every $n\ge1$, $X^n - 1 = \prod_{d\mid n} \Phi_d(X).$

Proof. A primitive $n$-th root $\zeta$ is also a $d$-th root whenever $d\mid n$, so $\zeta$ is a root of the product on the right. Both polynomials are monic of degree $n$, hence equal.

Theorem  For $n\ge1$ and $X\neq \pm1$,

$$\Phi_n(X) = \prod_{d\mid n} \bigl(X^{n/d} - 1\bigr)^{\mu(d)} = \prod_{d\mid n} \bigl(X^d - 1\bigr)^{\mu(n/d)}.$$

Proof. Apply the first theorem to the arithmetic function $f(n)=X^n-1$.

Main Theorem 

Statement. For every $n\ge1$, $\Phi_n(X) = \Phi_{\mathrm{rad}(n)}\bigl(X^{n/\mathrm{rad}(n)}\bigr).$

Proof. Write $r=\mathrm{rad}(n)$ and $k=n/r$ (so $k\ge1$ and $\gcd(k,r)=1$).

We have $\Phi_n(X) = \prod_{d\mid n} \bigl(X^{n/d} - 1\bigr)^{\mu(d)}.$ Because $\mu(d)=0$ whenever $d$ is not square-free, the only divisors $d$ that contribute are square-free, i.e. $d\mid r$. Replace $n/d$ by $(kr)/d$:

$$\Phi_n(X) = \prod_{d\mid r} \bigl(X^{k r / d} - 1\bigr)^{\mu(d)} = \prod_{d\mid r} \bigl((X^k)^{r/d} - 1\bigr)^{\mu(d)}.$$

Now compare with the formula of the 3rd theorem for $\Phi_r$, evaluated at $X^k$: $\Phi_r(X^k) = \prod_{d\mid r} \bigl((X^k)^{r/d} - 1\bigr)^{\mu(d)}.$ Hence $\Phi_n(X)=\Phi_r(X^k)=\Phi_r\bigl(X^{n/r}\bigr)$, as claimed.

To construct our new plaintext ring, we reduce $\Phi_{m}(X)$ modulo $t(X)$ by substituting $X^{k}=b$. Because $k\mid(m/r)$, this substitution yields a constant:

$$p = \Phi_{r}\bigl(b^{\,m/(rk)}\bigr)\in\mathbb{Z}$$

Hence the joint ideal $(\Phi_{m}(X),t(X))\subset\mathbb{Z}[X]$ collapses to $(t(X),p)$, giving us:

$$R_{p,t} = \mathbb{Z}[X]\big/(t(X),p)\;\cong\;\mathbb{Z}_{p}[X]\big/(X^{k}-b)$$

Lemma: Let $m\ge3$ and $r=\operatorname{rad}(m)$. Choose $0<k<\varphi(m)$ with $k\mid(m/r)$, and set $t(X)=X^{k}-b$. For $p = \Phi_{r}\bigl(b^{m/(rk)}\bigr)$, assume $p$ is prime and $p\nmid m$. Write $d=\operatorname{ord}_{m}(p)$.

Then $t(X)$ splits over $\mathbb{F}_{p}$ into $\ell' = \tfrac{k}{d}$ distinct irreducible factors of degree $d$. The Galois group is $\mathcal{G} = \{x\mapsto x^{i}\mid i\equiv1\pmod{m/k}\}$.

Why the Noise Stays Small

The crucial advantage of generalized BFV emerges from how we represent plaintexts in the new ring. When encrypting $\mu\in R_{p,t}$, we use the relation $X^{k}=b$ to find a representation with small coefficients:

$$\lVert[\mu]_{R}\rVert_{\infty}\le b$$

This is possible because the binomial relation lets us "carry" large powers into exponential form, keeping all coefficients bounded by $b-1$.

After $L$ multiplications, the worst-case coefficient grows like $b^{L}$, giving a depth bound:

$$L \lesssim \frac{\log q}{\log b}$$

Since $\log b \ll \log t$ (we choose $b$ to be small), this dramatically improves upon classical BFV's $\log q / \log t$ bound. The binomial modulus $t(X)=X^{k}-b$ enables far greater multiplicative depth without enlarging the ciphertext prime $q$.

SIMD Structure in Generalized BFV

For a comprehensive introduction to SIMD operations in FHE, see our previous post "One Ciphertext, Many Messages: SIMD operations in FHE".

Classical BFV enjoys $l$ independent SIMD slots:

$$R_p = \mathbb{Z}_p[X]/(X^{N}+1) = \mathbb{Z}_{p}[X]\big/(F_{1}(X)\big) \times \cdots \times \mathbb{Z}_{p}[X]\big/(F_{l}(X)\big)$$

Adding the binomial relation $X^{k}=b$ fundamentally changes this structure. We can understand the effect by thinking slot-wise:

For each slot, we "apply the quotient by $t(X)$" locally:

1. Evaluate $t(X)$ at the root of unity $\alpha$ that generates that slot
2. Quotient the slot's factor ring by the ideal $(t(\alpha))$

This creates two possibilities:

Condition on $t(\alpha)$	Resulting ideal	Effect on the slot
$t(\alpha)=0$	the zero ideal $(0)$	The slot remains unchanged
$t(\alpha)\neq0$	the whole ring $(1)$	The slot is completely eliminated

Consequently, a slot survives if and only if its root of unity $\alpha$ is a $k$-th root of $b$. Counting these roots yields exactly $\tfrac{k}{d}$ surviving slots, each operating over $\mathbb{F}_{p^{d}}$.

Viewing GBFV as a Subspace of Classical BFV

The relationship between generalized and classical BFV can be understood through the auxiliary prime $p = \Phi_r\bigl(b^{\,m/(rk)}\bigr)$.

Since $p$ lies in the ideal $(\Phi_m(X),t(X))$, we can express it as:

$$a(X)\,\Phi_m(X) + b(X)\,t(X) = p$$

where $a(X)$ and $b(X)$ are integer polynomials. Reducing modulo $\Phi_m$, this becomes:

$$p = \beta \cdot t(X)$$

where $\beta$ is $b(X)$ reduced modulo $\Phi_m(X)$. This gives us the fundamental relationship: $(p) = (\beta) \cdot (t)$ as ideals in $R$.

In the quotient ring $R_p = R/(p)$, we have $p \equiv 0$, which means:

$$0 = p = \beta \cdot t(X)$$

Since each slot behaves like a field, exactly one of $\beta$ or $t$ must be zero in each slot:

Slot type	Condition	Ideal
$\beta$-slot	$\beta=0$, $t\neq0$	$(\beta)$
$t$-slot	$t=0$, $\beta\neq0$	$(t)$

By the Chinese Remainder Theorem:

$$R_p \cong R/(\beta) \times R/(t) = R_{\beta} \times R_{t}$$

Generalized BFV makes its crucial choice here: it keeps only the $R_t$ block, eliminating all $\beta$-slots and preserving only the $t$-slots where $t(X) = 0$.

Hensel-Lifted Slots

Some applications, particularly bootstrapping, require a plaintext space defined modulo a prime power $p^{e}$ rather than just a prime $p$.

Our binomial ring construction adapts seamlessly to this requirement. Hensel's lemma allows us to lift the factorization:

$$\Phi_{m}(X)=\beta(X)\,t(X)\pmod{p}$$

to every power $p^{e}$ without changing the CRT slot structure.

We transition from field-level slots $\mathbb{F}_{p^{d}}$ to Galois rings:

$$R / \bigl(\Phi_m,\,p^{e},\,t\bigr) \;\cong\; \prod_{i \in S} \mathrm{GR}\!\left(p^{e},\,d\right)$$

This preserves the same $\tfrac{k}{d}$ SIMD lanes while providing coefficients modulo $p^{e}$. The Hensel lift provides the $p$-adic precision that bootstrapping requires, yet introduces no additional noise. After the ciphertext is refreshed, we can reduce back to modulus $p$ and continue the GBFV computation with all its low-noise advantages intact.

Bootstrapping Generalized BFV

The primary challenge with bootstrapping generalized BFV stems from its restricted structure: GBFV operates in a subring $R/(p,t) \subset R/(p)$, which severely limits the automorphisms available for bootstrapping.

The Core Problem: Missing Rotations

Standard BFV bootstrapping relies on access to the complete automorphism group:

$$\{\sigma_\ell : X \mapsto X^\ell \mid \ell \in (\mathbb{Z}/m\mathbb{Z})^\times\}$$

These rotations are essential for:

• Slot-wise permutations in digit extraction
• Baby-step/giant-step linear transforms
• Trace maps and diagonalization

However, in GBFV's quotient ring $R/(p,t)$ where $t(X) = X^k - b$, only rotations that preserve the ideal $(t)$ remain valid. This dramatically reduces the available automorphism group to:

$$\mathcal{G} = \{\sigma_\ell : \ell \equiv 1 \pmod{m/k}\}$$

We can only rotate within the $R_t$ block, we cannot access the rotations that would move between the $R_t$ and $R_\beta$ components of the full BFV ring.

The Solution: Lift, Pack, Bootstrap, Project

The key insight is to temporarily lift GBFV ciphertexts back to the full BFV ring $R/(p)$, where all necessary rotations become available.

Step 1: Pack Multiple GBFV Ciphertexts

Rather than bootstrapping a single GBFV ciphertext (which would waste the $R_\beta$ slots), we pack multiple GBFV ciphertexts into one BFV ciphertext. This ensures that every BFV slot contains meaningful data from some GBFV ciphertext, maximizing the efficiency of the bootstrap operation.

Step 2: Execute Standard BFV Bootstrap

With all slots filled, we run the standard BFV bootstrapping procedure. The bootstrap operation is agnostic to our packing scheme, it simply refreshes all slots in the full $R/(p)$ ring, where all required rotations are available.

Step 3: Project Back and Unpack

To recover individual GBFV ciphertexts:

1. Project the refreshed BFV ciphertext back to $R/(p,t)$ using the quotient map
2. Rotate as needed to extract the specific GBFV instance desired

The projection naturally eliminates the $R_\beta$ block while preserving the $R_t$ block. By performing appropriate rotations during unpacking, we can retrieve any of the GBFV ciphertexts that were packed into the original BFV ciphertext.

This approach transforms GBFV's fundamental limitation, its restricted automorphism group, into an advantage by enabling batch bootstrapping of multiple ciphertexts simultaneously.

Concrete Example

Let's work through a concrete example to illustrate the theory in practice.

Parameters

• Cyclotomic index: $m=8$, so $\Phi_8(X)=X^4+1$
• Binomial: $t(X)=X^2-b$ with $b=4$ and $k=2$
• Radical: $r=\mathrm{rad}(m)=2$
• Plaintext prime: $$p = \Phi_{r}\!\bigl(b^{\,m/(rk)}\bigr) = \Phi_{2}(4^{\,8/(2\cdot2)}) = \Phi_2(4^2)=\Phi_2(16)=16+1=17$$
• Residue degree: Since $p\equiv1\pmod{m}$, we have $d=\operatorname{ord}_m(p)=1$
• BFV slots: $n=\varphi(m)/d=\varphi(8)/1=4$

Classical BFV Slot Structure

We work in:

$$R_p = \mathbb{Z}[X] / \bigl(\Phi_8(X),p\bigr) \cong \mathbb{F}_{17}[X] / (X^4+1)$$

There is a primitive $8$-th root $\alpha=2\in\mathbb{F}_{17}$ since $2^8\equiv1$ and $2^4\equiv-1\pmod{17}$.
The four BFV slots correspond to evaluations at $\alpha^j$ for $j\in\{1,3,5,7\}=\mathbb{Z}_8^{*}$:

$$f(X) \longmapsto \bigl(f(\alpha), f(\alpha^3), f(\alpha^5), f(\alpha^7)\bigr)\in\mathbb{F}_{17}^4$$

Equivalently, we have the complete factorization:

$$X^4+1 = (X-2)(X-8)(X-15)(X-9)$$

Determining Slot Survival

To determine which slots survive after quotienting by $t(X)$, we use the rigorous slot-wise analysis: the quotient by $t(X)$ eliminates exactly those BFV slots where $t(\alpha)\neq0$ and preserves those where $t(\alpha)=0$.

Step 1: Reduce $t(X) = X^2-4 \mod 17$ and evaluate at the four roots $\alpha\in\{2,8,15,9\}$:

$$\overline{t}(X)=X^2-4, \quad \overline{t} \longmapsto \bigl(t(2), t(8), t(15), t(9)\bigr) = (0, 9, 0, 9)$$

Step 2: Under the Chinese Remainder Theorem, the principal ideal generated by $\overline{t}$ corresponds to:

$$\langle \overline{t}\rangle \longleftrightarrow \langle t(2)\rangle \times \langle t(8)\rangle \times \langle t(15)\rangle \times \langle t(9)\rangle \subset \mathbb{F}_{17}^4$$

Step 3: In a field $F$, we have $\langle a\rangle=\{0\}$ if $a=0$ and $\langle a\rangle=F$ if $a\neq0$. Therefore:

$$\langle t(2)\rangle=\{0\}, \quad \langle t(15)\rangle=\{0\}, \quad \langle t(8)\rangle=\mathbb{F}_{17}, \quad \langle t(9)\rangle=\mathbb{F}_{17}$$

So overall:

$$\langle \overline{t}\rangle \longleftrightarrow \{0\}\times \mathbb{F}_{17}\times \{0\}\times \mathbb{F}_{17}$$

Step 4: Taking the quotient coordinate-wise:

$$R_p / \langle \overline{t}\rangle \cong (\mathbb{F}_{17}/\{0\})\times(\mathbb{F}_{17}/\mathbb{F}_{17})\times (\mathbb{F}_{17}/\{0\})\times(\mathbb{F}_{17}/\mathbb{F}_{17}) \cong \mathbb{F}_{17}\times 0 \times \mathbb{F}_{17}\times 0$$

This shows that slots 1 and 3 survive (corresponding to roots $\alpha=2$ and $\alpha^5=15$), while slots 2 and 4 are eliminated.

Available Automorphisms in GBFV

Classical BFV automorphisms are $\sigma_i: X\mapsto X^{\,i}$ for $i\in\mathbb{Z}_8^{*}=\{1,3,5,7\}$.

After quotienting by $t(X)$, only those automorphisms that preserve the $(t)$-block remain valid. For $t(X)=X^k-b$, the surviving subgroup is:

$$\{i\in(\mathbb{Z}/m\mathbb{Z})^{*} : i\equiv1\pmod{m/k}\}$$

Here $m/k=8/2=4$, so $i\in\{1,5\}$.

Indeed, $\sigma_5$ swaps the two surviving slots, while $\sigma_3$ and $\sigma_7$ would send surviving slots to eliminated positions (making them invalid in $R/(p,t)$).

m = 8
p = 17
k = 2
b = 4


Fp       = GF(p)          # the base field F_p
R.<x>    = Fp[]           # polynomial ring F_p[x]
Phi      = cyclotomic_polynomial(m).change_ring(Fp)   # X^4 + 1 in F_p[x]
Rp       = R.quotient(Phi, 'Xbar')                    # Rp = F_p[x]/(Phi_m)
Xbar     = Rp.gen()


### Find a primitive m-th root of unity α in F_p (requires m | p-1)

g = Fp.multiplicative_generator()       # generator of F_p^*
alpha = g^((p - 1)//m)
assert alpha.multiplicative_order() == m, "No primitive m-th root in F_p; need extension field."

print("\nFound primitive %d-th root α in F_%d:" % (m, p), int(alpha))

### Classical BFV slot exponents: units mod m

slot_exps = [j for j in range(1, m) if gcd(j, m) == 1]
alphas    = [alpha^e for e in slot_exps]
print("\nBFV slot points α^j for j in (Z/%dZ)^* = %s:" % (m, slot_exps),
      [int(a) for a in alphas])

### Factorization over F_p (use Phi for clarity)

print("\nFactorization of Phi_%d(X) over F_%d:" % (m, p))
fac = Phi.factor()
print(" ", fac)

### Extract linear roots from the factorization and verify they match {alpha^j}

roots = []
for f, e in fac:              # linear factors f = x - r
    if f.degree() != 1:
        raise RuntimeError("Phi_m did not split linearly over F_p; need extension field.")
    r = -f[0]                 # r = -constant term
    roots.append(r)

### Check sets match (as multisets)

assert set(roots) == set(alphas), "Factorization roots != {alpha^j : j∈(Z/mZ)^*}"
print("Roots (some order):", [int(r) for r in roots])

### Survival under t(X) = X^k - b (here k=2, b=4)

t = x^k - b

t_vals = [t(a) for a in alphas]
survivor_mask = [(tv == Fp(0)) for tv in t_vals]  # survive iff t(α)=0

print("\nEvaluate t(X)=X^%d-%d at slot points:" % (k, b))
for j, a, tv in zip(slot_exps, alphas, t_vals):
    status = "SURVIVES" if tv == 0 else "KILLED"
    print(f"  t(α^{j}) = t({int(a)}) = {int(tv):2d}  ->  {status}")

Conclusion

Generalized BFV with polynomial quotients represents a significant advance in practical fully homomorphic encryption. By replacing the classical integer plaintext modulus with carefully chosen binomial relations $t(X) = X^k - b$, we escape the fundamental trade-off between data packing and multiplicative depth that has constrained classical BFV.

The key insights are:

1. Noise control: The binomial relation enables coefficient representations bounded by $b$, leading to noise growth $\sim b^L$ rather than $\sim t^L$
2. Depth scaling: Multiplicative depth scales as $\log q / \log b$ instead of $\log q / \log t$, dramatically improving when $b \ll t$
3. Structured slots: The quotient construction naturally creates a subspace of classical BFV slots with well-understood algebraic structure
4. Bootstrapping solution: Temporary lifting to the full BFV ring enables batch bootstrapping of multiple GBFV ciphertexts

These advances open new possibilities for applications requiring both high throughput and deep computation, bringing FHE closer to practical deployment in privacy-preserving machine learning, secure database operations, and encrypted analytics.

The generalized BFV construction demonstrates that fundamental limitations in cryptographic schemes can sometimes be overcome not by abandoning existing frameworks, but by recognizing and exploiting the deeper algebraic structures they contain.

Acknowledgments

This work builds upon the foundational research presented in two key papers that introduced and developed the generalized BFV framework. We gratefully acknowledge the contributions of the authors of "Fully Homomorphic Encryption for Cyclotomic Prime Moduli" and "MatriGear: Accelerating Authenticated Matrix Triple Generation with Scalable Prime Fields via Optimized HE Packing". Their innovative approach to polynomial quotient constructions and rigorous analysis of noise behavior provided the theoretical foundation that made this exposition possible. The mathematical insights and practical considerations presented in these works have significantly advanced the field of fully homomorphic encryption and enabled new possibilities for privacy-preserving computation.