Relaxed Functional Bootstrapping: A New Perspective on BGV/BFV Bootstrapping¶
Authors: Zeyu Liu; Yunhao Wang
Year: 2025
Venue: Lecture Notes in Computer Science
type: technique collection: schemes status: auto
Links: DOI · ePrint 2024/172 · Semantic Scholar
Summary¶
Auto-extracted summary (unreviewed)
The paper relaxes the correctness requirement of BGV/BFV bootstrapping so that only inputs from a subset of the plaintext space need to be refreshed, and lets the bootstrapping output a function of the input (functional bootstrapping), with specialised constructions for identity, point and range functions. The resulting procedure is 1-2 orders of magnitude faster than state-of-the-art BGV/BFV bootstrapping depending on the function, and the same technique speeds up batched FHEW/TFHE bootstrapping by 6x in latency and 3x in throughput for binary gates.
Abstract¶
BGV and BFV are among the most widely used fully homomorphic encryption (FHE) schemes, supporting evaluations over a finite field. To evaluate a circuit with arbitrary depth, bootstrapping is needed. However, despite the recent progress, bootstrapping of BGV/BFV still remains relatively impractical, compared to other FHE schemes. In this work, we inspect the BGV/BFV bootstrapping procedure from a different angle. We provide a generalized bootstrapping definition that relaxes the correctness requirement of regular bootstrapping, allowing constructions that support only certain kinds of circuits with arbitrary depth. In addition, our definition captures a form of functional bootstrapping. In other words, the output encrypts a function evaluation of the input instead of the input itself. Under this new definition, we provide a bootstrapping procedure supporting different types of functions. Our construction is 1-2 orders of magnitude faster than the state-of-the-art BGV/BFV bootstrapping algorithms, depending on the evaluated function. Of independent interest, we show that our technique can be used to improve the batched FHEW/TFHE bootstrapping construction introduced by Liu and Wang (Asiacrypt 2023). Our optimization provides a speed-up of 6x in latency and 3x in throughput for batched binary gate bootstrapping and a plaintextspace-dependent speed-up for batched functional bootstrapping with plaintext space smaller than Z512. 1 Contents
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | generalised (relaxed) bootstrapping definition for BGV/BFV capturing functional bootstrapping | llm | 0.75 |
| contribution | general bootstrapping framework for identity, point and range functions over subsets of Z_t | llm | 0.75 |
| contribution | 1-2 orders of magnitude speed-up over state-of-the-art BGV/BFV bootstrapping | llm | 0.75 |
| contribution | improved batched FHEW/TFHE bootstrapping (6x latency, 3x throughput for binary gates) | llm | 0.75 |
| contribution | applications such as oblivious permutation via BFV | llm | 0.75 |
| schemes | BGV | llm | 0.75 |
| schemes | BFV | llm | 0.75 |
| schemes | FHEW | llm | 0.75 |
| schemes | TFHE | llm | 0.75 |
| tasks | FHE bootstrapping | llm | 0.75 |
| tasks | oblivious permutation | llm | 0.75 |
| tasks | PSI with computation | llm | 0.75 |
| tasks | secure machine learning (as application domain) | llm | 0.75 |
| security level | >128-bit (LWE estimator) for all but one function; statistical parameter 40 | llm | 0.75 |
| interaction | non-interactive FHE | llm | 0.75 |
| code url | http://github.com/ldsec/lattigo (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/homenc/HElib (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/Microsoft/SEAL (URL found in the full text) | regex | 0.50 |
| limitations | supports only circuits whose bootstrapping inputs/outputs lie in a subset of the plaintext space rather than arbitrary circuits | llm | 0.75 |
| limitations | one evaluated function (fub) does not reach the 128-bit security guaranteed for the others | llm | 0.75 |
| llm relevance | low | llm | 0.75 |
| key result | bootstrapping speed-up: 1-2 orders of magnitude (vs state-of-the-art BGV/BFV bootstrapping, depending on evaluated function) | llm | 0.75 |
| key result | batched binary-gate bootstrapping speed-up: 6x latency, 3x throughput (vs Liu-Wang (Asiacrypt 2023) batched FHEW/TFHE bootstrapping) | llm | 0.75 |
| key result | batched functional bootstrapping speed-up: plaintext-space-dependent (plaintext space smaller than Z_512) | llm | 0.75 |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: BFV 158 [p.1], BGV 18 [p.1], CKKS 16 [p.6], FHEW 15 [p.1], TFHE 13 [p.1], PIR 6 [p.29], Leveled / somewhat HE 4 [p.2]
- library: HElib 4 [p.33], Microsoft SEAL 3 [p.25], Lattigo 1 [p.32]
- hardware: Intel Xeon 2 [p.27]
- technique: Bootstrapping 231 [p.1], Functional bootstrapping 40 [p.1], Rotations 16 [p.8], Modulus switching 12 [p.7], Lookup table 7 [p.4], SIMD packing 6 [p.3], NTT 5 [p.16], Matrix multiplication 5 [p.8], Key switching 2 [p.16], Polynomial approximation 2 [p.28], Paterson-Stockmeyer 2 [p.17]
- assumption: LWE 25 [p.4], 128-bit security 6 [p.25], RLWE 4 [p.5]
- task: Language modeling / generation 5 [p.8]
- topic: Homomorphic encryption 41 [p.1], Benchmark 9 [p.4], Open source 4 [p.32]
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-2_eprint-2024-172.pdf |
schemes | 35 | 1.1 MB | 47ab2631fc5d |
Database key: relaxed-functional-bootstrapping-a-new-perspective-on-bgv-bfv · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set relaxed-functional-bootstrapping-a-new-perspective-on-bgv-bfv COLUMN VALUE