(Leveled) Fully Homomorphic Encryption without Bootstrapping¶
Authors: Z. Brakerski; C. Gentry; V. Vaikuntanathan
Year: 2012
Venue: ITCS 2012
type: scheme collection: catalogue, schemes, sok-references status: auto
Links: ePrint 2011/277
Visual lesson: BGV · Scheme table row: BGV
Summary¶
Auto-extracted summary (unreviewed)
Brakerski, Gentry and Vaikuntanathan introduce the BGV approach to leveled fully homomorphic encryption, which evaluates arbitrary polynomial-size circuits without Gentry's bootstrapping by controlling ciphertext noise through modulus switching, using techniques from Brakerski-Vaikuntanathan (FOCS 2011). Based on LWE or RLWE with 2^lambda security, the RLWE variant achieves O~(lambda * L^3) per-gate computation for L-level circuits without bootstrapping, or O~(lambda^2) per gate independent of L when bootstrapping is used as an optimization under quasi-polynomial RLWE hardness, and O~(lambda) per gate with batched bootstrapping for wide circuits, versus Omega~(lambda^3.5) for all previous schemes.
Abstract¶
We present a radically new approach to fully homomorphic encryption (FHE) that dramatically improves performance and bases security on weaker assumptions. A central conceptual contribution in our work is a new way of constructing leveled fully homomorphic encryption schemes (capable of evaluating arbitrary polynomial-size circuits), without Gentry’s bootstrapping procedure. Specifically, we offer a choice of FHE schemes based on the learning with error (LWE) or ring-LWE (RLWE) problems that have 2λ security against known attacks. For RLWE, we have: • A leveled FHE scheme that can evaluate L-level arithmetic circuits with ˜O(λ · L3) per-gate computation – i.e., computation quasi-linear in the security parameter. Security is based on RLWE for an approximation factor exponential in L. This construction does not use the bootstrapping procedure. • A leveled FHE scheme that uses bootstrapping as an optimization, where the per-gate computation (which includes the bootstrapping procedure) is ˜O(λ2), independent of L. Security is based on the hardness of RLWE for quasi-polynomial factors (as opposed to the sub-exponential factors needed in previous schemes). We obtain similar results for LWE, but with worse performance. We introduce a number of further optimizations to our schemes. As an example, for circuits of large width – e.g., where a constant fraction of levels have width at least λ – we can reduce the per-gate computation of the bootstrapped version to ˜O(λ), independent of L, by batching the bootstrapping operation. Previous FHE schemes all required ˜Ω(λ3.5) computation per gate. At the core of our construction is a much more effective approach for managing the noise level of lattice-based ciphertexts as homomorphic operations are performed, using some new techniques recently introduced by Brakerski and Vaikuntanathan (FOCS 2011). ∗Sponsored by the Air Force Research Laboratory (AFRL). Disclaimer: This material is based on research sponsored by DARPA under agreement number FA8750-11-C-0096 and FA8750-11-2-0225. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of DARPA or the U.S. Government. Approved for Public Release, Distribution Unlimited. †This material is based on research sponsored by DARPA under Agreement number FA8750-11-2-0225. All disclaimers as above apply.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | Leveled FHE construction without bootstrapping via modulus switching noise management | llm | 0.85 |
| contribution | RLWE-based scheme with O~(lambda * L^3) per-gate computation for L-level circuits | llm | 0.85 |
| contribution | Bootstrapping as an optimization yielding O~(lambda^2) per-gate computation independent of L under quasi-polynomial RLWE hardness | llm | 0.85 |
| contribution | Batched bootstrapping reducing per-gate cost to O~(lambda) for wide circuits | llm | 0.85 |
| contribution | LWE-based variants with weaker performance | llm | 0.85 |
| schemes | BGV | llm | 0.85 |
| security level | 2^lambda security against known attacks (asymptotic) | llm | 0.85 |
| interaction | non-interactive FHE | llm | 0.85 |
| limitations | LWE-based variants have worse performance than the RLWE variants | llm | 0.85 |
| limitations | Non-bootstrapped leveled variant relies on RLWE hardness for an approximation factor exponential in L | llm | 0.85 |
| llm relevance | low | llm | 0.85 |
| key result | per-gate computation: O~(lambda * L^3) (RLWE leveled scheme, no bootstrapping, L-level circuits) | llm | 0.85 |
| key result | per-gate computation: O~(lambda^2), independent of L (RLWE scheme with bootstrapping as optimization, quasi-polynomial RLWE factors) | llm | 0.85 |
| key result | per-gate computation: O~(lambda) (batched bootstrapping for circuits of width at least lambda) | llm | 0.85 |
| key result | prior per-gate computation: Omega~(lambda^3.5) (all previous FHE schemes) | llm | 0.85 |
Scheme card: BGV¶
| Group | 2. Exact word-wise FHE (BGV / BFV family) |
| Kind | Scheme |
| Hardness assumption | RLWE / LWE |
| Plaintext type | Exact integers mod p |
| SIMD packing | Yes |
| Bootstrapping | Yes, slow (digit extraction) |
| Post-quantum | Yes |
| Status | Widely used |
| Fit for LLM inference | Exact arithmetic suits integer-quantized LLMs, but there is no cheap rescaling of real values and bootstrapping is costly. |
| Follow-ups | Bootstrapping for BGV and BFV revisited (2022/1363); relaxed functional bootstrapping (2024/172). |
| Libraries | OpenFHE, HElib, SEAL, Lattigo |
| Follow-up papers in the archive | Bootstrapping for BGV and BFV Revisited Relaxed Functional Bootstrapping: A New Perspective on BGV/BFV Bootstrapping |
System card: BGV¶
| Group | 4. Alternative FHE schemes |
| Family | RLWE, leveled, modulus switching |
| Arithmetic | Exact integers mod p, SIMD |
| Interaction | Non-interactive |
| Model scale | CNNs, quantized models |
| Status | Widely used |
| Relation to the SoK | Exact counterpart of CKKS with plaintext modulus p. |
| Note | Exact arithmetic suits quantized integer LLMs. Non-linear functions and bootstrapping are costlier than in CKKS. |
| Code | https://github.com/homenc/HElib |
| Systems page | BGV |
SoK reference [63]¶
Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(Leveled) fully homomorphic encryption without bootstrapping,” in ITCS 2012: 3rd Innovations in Theoretical Computer Science, S. Goldwasser, Ed. Cambridge, MA, USA: Association for Computing Machinery, Jan. 8–10, 2012, pp. 309–325.
Listed on the reference page of the site.
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: Leveled / somewhat HE 28 [p.1]
- technique: Bootstrapping 85 [p.1], Modulus switching 18 [p.4], Key switching 7 [p.9], Rotations 3 [p.23], Relinearization 2 [p.8]
- assumption: RLWE 40 [p.1], LWE 37 [p.1], Lattice-based 24 [p.1]
- topic: Homomorphic encryption 118 [p.1]
Related papers¶
- Bootstrapping for BGV and BFV Revisited follow up of this paper — follow-up listed for scheme "BGV"
- Relaxed Functional Bootstrapping: A New Perspective on BGV/BFV Bootstrapping follow up of this paper — follow-up listed for scheme "BGV"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/4-048_leveled-fully-homomorphic-encryption-without-bootstrapping.pdf |
catalogue | 27 | 424.4 KB | 3a09cfaa3a91 |
|
references/schemes/s14-0_leveled-fully-homomorphic-encryption-without-bootstrapping.pdf |
schemes | 27 | 424.4 KB | 3a09cfaa3a91 |
byte-identical to references/catalogue/4-048_leveled-fully-homomorphic-encryption-without-bootstrapping.pdf |
references/sok-references/063_leveled-fully-homomorphic-encryption-without-bootstrapping.pdf |
sok-references | 27 | 424.4 KB | 3a09cfaa3a91 |
byte-identical to references/catalogue/4-048_leveled-fully-homomorphic-encryption-without-bootstrapping.pdf |
Database key: leveled-fully-homomorphic-encryption-without-bootstrapping · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set leveled-fully-homomorphic-encryption-without-bootstrapping COLUMN VALUE