Skip to content

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]

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