Bootstrapping for BGV and BFV Revisited¶
Authors: Robin Geelen; Frederik Vercauteren
Year: 2022
type: technique collection: schemes status: auto
Links: ePrint 2022/1363
Summary¶
Auto-extracted summary (unreviewed)
Unifies the state-of-the-art bootstrapping algorithms for BGV and BFV into a single framework and shows both schemes bootstrap with identical complexity, correcting the Chen-Han claim that BFV is cheaper to bootstrap and fixing an error in their power-of-two cyclotomic procedure. The paper compares Halevi-Shoup and Chen-Han linear transformations and digit extraction, and releases the first open-source library (in Magma) supporting both BGV and BFV bootstrapping in full generality.
Abstract¶
We unify the state-of-the-art bootstrapping algorithms for BGV and BFV in a single framework, and show that both schemes can be bootstrapped with identical complexity. This result corrects a claim by Chen and Han (Eurocrypt 2018) that BFV is more efficient to bootstrap than BGV. We also fix an error in their optimized procedure for powerof-two cyclotomics, which occurs for some parameter sets. Our analysis is simpler, yet more general than earlier work, in that it simultaneously covers both BGV and BFV. Furthermore, we also design and implement a high-level open source software library for bootstrapping in the Magma Computer Algebra System. It is the first library to support both BGV and BFV bootstrapping in full generality, with all recent techniques (including the above fixes) and trade-offs.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | unified framework for BGV and BFV bootstrapping with identical complexity | llm | 0.85 |
| contribution | correction of Chen-Han's claim that BFV bootstraps more efficiently than BGV | llm | 0.85 |
| contribution | fix of an error in the optimized power-of-two cyclotomic procedure | llm | 0.85 |
| contribution | asymptotic cost comparison of Halevi-Shoup vs Chen-Han linear transformations and digit extraction | llm | 0.85 |
| contribution | open-source high-level bootstrapping library in the Magma Computer Algebra System | llm | 0.85 |
| schemes | BGV | llm | 0.85 |
| schemes | BFV | llm | 0.85 |
| libraries | Magma | llm | 0.85 |
| tasks | FHE bootstrapping | llm | 0.85 |
| tasks | exact modular arithmetic on encrypted data | llm | 0.85 |
| interaction | non-interactive FHE | llm | 0.85 |
| code url | https://github.com/homenc/HElib (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/KULeuven-COSIC/Bootstrapping (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/KULeuven-COSIC/Bootstrapping_BGV_BFV | llm | 0.85 |
| limitations | digit extraction remains the bottleneck because of the many key-switching operations | llm | 0.85 |
| limitations | implementation is a high-level Magma library rather than an optimized low-level implementation | llm | 0.85 |
| llm relevance | low | llm | 0.85 |
| key result | linear transformation cost (one-dimensional, good dimension, sparse slots): 2sqrt(l_i) + O(1) automorphisms and l_i constant multiplications (baby-step/giant-step implementation)* | llm | 0.85 |
| key result | polynomial evaluation cost: 2sqrt(n) + O(log^2 n) ciphertext-ciphertext multiplications, depth ceil(log2 n) (degree-n polynomial via baby-step/giant-step)* | llm | 0.85 |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: BFV 68 [p.1], BGV 67 [p.1], Leveled / somewhat HE 6 [p.2], CKKS 4 [p.2], PIR 2 [p.2]
- library: HElib 8 [p.2], Microsoft SEAL 1 [p.2]
- technique: Bootstrapping 102 [p.1], Rotations 8 [p.7], Modulus switching 5 [p.6], Key switching 4 [p.5], SIMD packing 4 [p.2], Matrix multiplication 2 [p.2]
- assumption: RLWE 5 [p.4], LWE 2 [p.4], Lattice-based 2 [p.11]
- topic: Homomorphic encryption 28 [p.1], Open source 4 [p.2]
Related papers¶
- this paper follow up of (Leveled) Fully Homomorphic Encryption without Bootstrapping — follow-up listed for scheme "BGV"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s14-1_eprint-2022-1363.pdf |
schemes | 32 | 520.5 KB | 34888948381c |
Database key: bootstrapping-for-bgv-and-bfv-revisited · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set bootstrapping-for-bgv-and-bfv-revisited COLUMN VALUE