Skip to content

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]

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