Skip to content

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]

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