Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP¶
Authors: Z. Brakerski
Year: 2012
Venue: CRYPTO 2012
type: scheme collection: catalogue, schemes, sok-references status: auto
Links: ePrint 2012/78 · link
Summary¶
Auto-extracted summary (unreviewed)
Brakerski introduces a new tensoring technique for LWE-based FHE under which ciphertext noise grows only linearly (B to B*poly(n)) per multiplication instead of quadratically, yielding a scale-invariant scheme whose properties depend only on the ratio q/B. The scheme keeps a single, arbitrary-form modulus throughout evaluation (no modulus switching) and its security is reduced classically from worst-case GapSVP with quasi-polynomial approximation factor, where earlier constructions had only quantum reductions.
Abstract¶
We present a new tensoring technique for LWE-based fully homomorphic encryption. While in all previous works, the ciphertext noise grows quadratically (B →B2 · poly(n)) with every multiplication (before “refreshing”), our noise only grows linearly (B →B · poly(n)). We use this technique to construct a scale-invariant fully homomorphic encryption scheme, whose properties only depend on the ratio between the modulus q and the initial noise level B, and not on their absolute values. Our scheme has a number of advantages over previous candidates: It uses the same modulus throughout the evaluation process (no need for “modulus switching”), and this modulus can take arbitrary form. In addition, security can be classically reduced from the worst-case hardness of the GapSVP problem (with quasi-polynomial approximation factor), whereas previous constructions could only exhibit a quantum reduction from GapSVP. ∗Stanford University, zvika@stanford.edu. Supported by a Simons Postdoctoral Fellowship and by DARPA.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | Tensoring technique with linear (rather than quadratic) noise growth per homomorphic multiplication | llm | 0.85 |
| contribution | Scale-invariant FHE scheme depending only on the ratio q/B | llm | 0.85 |
| contribution | Elimination of modulus switching; the modulus can take arbitrary form | llm | 0.85 |
| contribution | Classical reduction from worst-case GapSVP with quasi-polynomial approximation factor | llm | 0.85 |
| schemes | LWE-based scale-invariant FHE (Brakerski) | llm | 0.85 |
| schemes | GapSVP | llm | 0.85 |
| tasks | general homomorphic evaluation / outsourced computation | llm | 0.85 |
| interaction | non-interactive FHE | llm | 0.85 |
| llm relevance | low | llm | 0.85 |
| key result | noise growth per multiplication: B -> Bpoly(n) (linear) vs B -> B^2poly(n) (quadratic) previously (LWE-based FHE before refreshing) | llm | 0.85 |
System card: Brakerski scale-invariant FHE¶
| Group | 4. Alternative FHE schemes |
| Family | LWE, scale-invariant |
| Arithmetic | Exact integers |
| Interaction | Non-interactive |
| Model scale | - |
| Status | Foundational |
| Relation to the SoK | Theoretical basis of BFV. |
| Note | Removes modulus switching through scale invariance. |
| Systems page | Brakerski scale-invariant FHE |
SoK reference [64]¶
Z. Brakerski, “Fully homomorphic encryption without modulus switching from classical GapSVP,” in Advances in Cryptology – CRYPTO 2012, ser. Lecture Notes in Computer Science, R. SafaviNaini and R. Canetti, Eds., vol. 7417. Santa Barbara, CA, USA: Springer Berlin Heidelberg, Germany, Aug. 19–23, 2012, pp. 868– 886.
Listed on the reference page of the site.
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- technique: Bootstrapping 16 [p.4], Key switching 11 [p.5], Modulus switching 4 [p.1]
- assumption: LWE 28 [p.1], Lattice-based 22 [p.2], RLWE 6 [p.3]
- topic: Homomorphic encryption 59 [p.1]
Related papers¶
- this paper follow up of Somewhat Practical Fully Homomorphic Encryption — follow-up listed for scheme "BFV"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/4-050_fully-homomorphic-encryption-without-modulus-switching-from.pdf |
catalogue | 20 | 171.2 KB | 0abfedb6e370 |
|
references/schemes/s15-1_eprint-2012-078.pdf |
schemes | 20 | 171.2 KB | 0abfedb6e370 |
byte-identical to references/catalogue/4-050_fully-homomorphic-encryption-without-modulus-switching-from.pdf |
references/sok-references/064_fully-homomorphic-encryption-without-modulus-switching-from.pdf |
sok-references | 20 | 171.2 KB | 0abfedb6e370 |
byte-identical to references/catalogue/4-050_fully-homomorphic-encryption-without-modulus-switching-from.pdf |
Database key: fully-homomorphic-encryption-without-modulus-switching-from-classical · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set fully-homomorphic-encryption-without-modulus-switching-from-classical COLUMN VALUE