Skip to content

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]

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