Fully Homomorphic Encryption for Cyclotomic Prime Moduli¶
Authors: Geelen, Vercauteren
Year: 2025
Venue: EUROCRYPT 2025
type: scheme collection: schemes status: auto
Links: ePrint 2024/1587
Visual lesson: Generalized BFV (GBFV) · Scheme table row: Generalized BFV (GBFV)
Summary¶
Auto-extracted summary (unreviewed)
The paper introduces Generalized BFV (GBFV), which encrypts plaintext spaces Z[x]/(Phi_m(x), t(x)) for an arbitrary polynomial t(x), unifying BFV (constant t) and CLPX (linear t) and combining BFV's SIMD packing with CLPX's low noise growth while remaining bootstrappable. Parameter families natively support large cyclotomic primes such as the Fermat prime 2^16+1 and the Goldilocks prime, and because of the lower noise growth GBFV can be bootstrapped at 128-bit security with ring dimension n = 2^14. An implementation on top of SEAL bootstraps a ciphertext holding up to 8192 elements modulo 2^16+1 in about 2 seconds on an Apple M1 Max.
Abstract¶
This paper presents a Generalized BFV (GBFV) fully homomorphic encryption scheme that encrypts plaintext spaces of the form Z[x]/(Φm(x), t(x)) with Φm(x) the m-th cyclotomic polynomial and t(x) an arbitrary polynomial. GBFV encompasses both BFV where t(x) = p is a constant, and the CLPX scheme (CT-RSA 2018) where m = 2k and t(x) = x −b is a linear polynomial. The latter can encrypt a single huge integer modulo Φm(b), has much lower noise growth than BFV, but it is not known to be efficiently bootstrappable. We show that by a clever choice of m and higher degree polynomial t(x), our scheme combines the SIMD capabilities of BFV with the low noise growth of CLPX, whilst still being efficiently bootstrappable. Moreover, we present parameter families that natively accommodate packed plaintext spaces defined by a large cyclotomic prime, such as the Fermat prime Φ2(216) = 216+1 and the Goldilocks prime Φ6(232) = 264−232+1. These primes are often used in homomorphic encryption applications and zeroknowledge proof systems. Due to the lower noise growth, GBFV can evaluate much deeper circuits compared to native BFV in the same ring dimension. As a result, we can evaluate either larger circuits or work with smaller ring dimensions. In particular, we can natively bootstrap GBFV at 128-bit security already at ring dimension n = 214, which was impossible before. We implemented the GBFV scheme on top of the SEAL library and achieve a latency of only 2 seconds to bootstrap a ciphertext encrypting up to 8192 elements modulo 216 + 1.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | Generalized BFV scheme with polynomial plaintext modulus t(x) encompassing BFV and CLPX | llm | 0.90 |
| contribution | Combination of SIMD slots with CLPX-like low noise growth while keeping efficient bootstrapping | llm | 0.90 |
| contribution | Parameter families for cyclotomic primes such as the Fermat prime 2^16+1 and the Goldilocks prime 2^64-2^32+1 | llm | 0.90 |
| contribution | Native bootstrapping at 128-bit security with ring dimension n = 2^14 | llm | 0.90 |
| contribution | Implementation on Microsoft SEAL extending the BFV bootstrapping of Geelen with sparse secret encapsulation | llm | 0.90 |
| contribution | Single and batch bootstrapping benchmarks | llm | 0.90 |
| schemes | GBFV | llm | 0.90 |
| schemes | BFV | llm | 0.90 |
| schemes | CLPX | llm | 0.90 |
| schemes | BGV | llm | 0.90 |
| libraries | SEAL | llm | 0.90 |
| tasks | high-precision integer arithmetic | llm | 0.90 |
| tasks | bootstrapping | llm | 0.90 |
| tasks | zero-knowledge proof system arithmetic (motivation) | llm | 0.90 |
| hardware | Apple M1 Max (MacBook Pro 2021, 64 GB RAM) | llm | 0.90 |
| security level | 128-bit | llm | 0.90 |
| interaction | non-interactive FHE | llm | 0.90 |
| code url | https://github.com/KULeuven-COSIC/Bootstrapping (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/matter-labs/era-boojum (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/0xPolygonMiden/miden-vm (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/KULeuven-COSIC/Bootstrapping_BGV_BFV | llm | 0.90 |
| limitations | SEAL only supports power-of-two cyclotomic rings and moduli of at most 60 bits, so not all recommended parameter sets could be implemented | llm | 0.90 |
| limitations | Using all 16384 slots (regular BFV) is impossible for the benchmark parameters because the remaining noise budget would be negative | llm | 0.90 |
| limitations | Batch bootstrapping has higher latency than single bootstrapping because multiple digit-removal polynomials are evaluated | llm | 0.90 |
| llm relevance | low | llm | 0.90 |
| key result | single bootstrapping latency: 1.94-2.01 s (m = 2^15, p = 2^16+1, 1024 to 8192 slots, Apple M1 Max) | llm | 0.90 |
| key result | remaining noise budget after bootstrapping: 124 bits (1024 slots) down to 38 bits (8192 slots) (single bootstrapping, q about 2^420) | llm | 0.90 |
| key result | ring dimension at 128-bit security: n = 2^14 with at least 1024 slots (previously impossible for native BFV bootstrapping) | llm | 0.90 |
| key result | bootstrapping failure rate: less than 2^-64 (noise cut-off B = 15, sparse key Hamming weight 32) | llm | 0.90 |
| key result | throughput: up to 186e3 slotsbits/s (4096 slots single bootstrapping)* | llm | 0.90 |
Scheme card: Generalized BFV (GBFV)¶
| Group | 2. Exact word-wise FHE (BGV / BFV family) |
| Kind | Scheme |
| Hardness assumption | RLWE |
| Plaintext type | Exact, polynomial plaintext modulus t(x) |
| SIMD packing | Yes, tunable |
| Bootstrapping | Yes |
| Post-quantum | Yes |
| Status | Active SOTA |
| Fit for LLM inference | Unifies BFV and CLPX and trades SIMD width for precision. A flexible exact alternative to CKKS. |
| Follow-ups | Bootstrapping GBFV with CKKS (2025/888); FHE on the ring of Gaussian periods (CT-RSA 2026, 2026/927). |
| Follow-up papers in the archive | Bootstrapping GBFV with CKKS Fully Homomorphic Encryption on the Ring of Gaussian Periods |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: BFV 91 [p.1], BGV 18 [p.1], CKKS 7 [p.1], Zero-knowledge proofs 5 [p.3], TFHE 3 [p.1], FHEW 3 [p.1], NTRU 2 [p.3], RSA 2 [p.1]
- library: Microsoft SEAL 9 [p.1], HElib 6 [p.5]
- hardware: Apple silicon 1 [p.25]
- technique: Bootstrapping 85 [p.1], SIMD packing 11 [p.1], Key switching 5 [p.13], Functional bootstrapping 3 [p.20], Modulus switching 2 [p.27], Rotations 2 [p.16]
- assumption: RLWE 20 [p.4], LWE 19 [p.4], Lattice-based 6 [p.28], 128-bit security 3 [p.1]
- topic: Homomorphic encryption 46 [p.1], Open source 6 [p.3], Benchmark 2 [p.25]
Related papers¶
- Bootstrapping GBFV with CKKS follow up of this paper — follow-up listed for scheme "Generalized BFV (GBFV)"
- Fully Homomorphic Encryption on the Ring of Gaussian Periods follow up of this paper — follow-up listed for scheme "Generalized BFV (GBFV)"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s17-0_fully-homomorphic-encryption-for-cyclotomic-prime-moduli.pdf |
schemes | 32 | 580.5 KB | 3158eb77d6ae |
Database key: fully-homomorphic-encryption-for-cyclotomic-prime-moduli · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set fully-homomorphic-encryption-for-cyclotomic-prime-moduli COLUMN VALUE