Efficient Fully Homomorphic Encryption from (Standard) LWE¶
Authors: Brakerski, Vaikuntanathan
Year: 2011
Venue: FOCS 2011
type: scheme collection: schemes status: auto
Links: ePrint 2011/344
Visual lesson: BV11 (FHE from LWE) · Scheme table row: BV11 (FHE from LWE)
Summary¶
Auto-extracted summary (unreviewed)
Constructs a fully homomorphic encryption scheme whose security rests solely on the standard LWE assumption (hence worst-case hardness of lattice problems on arbitrary, not ideal, lattices). A new relinearization technique gives somewhat-homomorphic encryption from LWE, and a dimension-modulus reduction technique replaces Gentry's squashing step, removing the sparse-subset-sum assumption and yielding very short ciphertexts; these are used to build an asymptotically efficient single-server PIR protocol with k*polylog(k)+log|DB| bits of communication per single-bit query.
Abstract¶
We present a fully homomorphic encryption scheme that is based solely on the (standard) learning with errors (LWE) assumption. Applying known results on LWE, the security of our scheme is based on the worst-case hardness of “short vector problems” on arbitrary lattices. Our construction improves on previous works in two aspects: 1. We show that “somewhat homomorphic” encryption can be based on LWE, using a new relinearization technique. In contrast, all previous schemes relied on complexity assumptions related to ideals in various rings. 2. We deviate from the “squashing paradigm” used in all previous works. We introduce a new dimension-modulus reduction technique, which shortens the ciphertexts and reduces the decryption complexity of our scheme, without introducing additional assumptions. Our scheme has very short ciphertexts and we therefore use it to construct an asymptotically efficient LWE-based single-server private information retrieval (PIR) protocol. The communication complexity of our protocol (in the public-key model) is k · polylog(k) + log |DB| bits per single-bit query (here, k is a security parameter). ∗Weizmann Institute of Science. Email: zvika.brakerski@weizmann.ac.il. The author’s research was supported by ISF grant 710267, BSF grant 710613, and NSF contracts CCF-1018064 and CCF-0729011. †University of Toronto. Email: vinodv@cs.toronto.edu.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | Somewhat homomorphic encryption from standard LWE via relinearization | llm | 0.85 |
| contribution | Dimension-modulus reduction replacing the squashing paradigm (no sparse subset-sum assumption) | llm | 0.85 |
| contribution | FHE based on worst-case hardness of short-vector problems on arbitrary lattices | llm | 0.85 |
| contribution | Short ciphertexts enabling an efficient LWE-based single-server PIR protocol | llm | 0.85 |
| schemes | LWE-based FHE (Brakerski-Vaikuntanathan) | llm | 0.85 |
| schemes | PIR | llm | 0.85 |
| tasks | private information retrieval | llm | 0.85 |
| interaction | non-interactive FHE | llm | 0.85 |
| llm relevance | low | llm | 0.85 |
| key result | PIR communication complexity: kpolylog(k) + log|DB| bits per single-bit query (public-key model, k = security parameter)* | llm | 0.85 |
Scheme card: BV11 (FHE from LWE)¶
| Group | 5. Earlier and other FHE constructions |
| Kind | Scheme |
| Hardness assumption | LWE |
| Plaintext type | Bits |
| SIMD packing | No |
| Bootstrapping | Yes |
| Post-quantum | Yes |
| Status | Foundational |
| Fit for LLM inference | First FHE from standard LWE. Its relinearization and modulus switching are used by all modern schemes. |
| Follow-ups | Ring-LWE version: Brakerski–Vaikuntanathan CRYPTO 2011. |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: PIR 59 [p.1], Leveled / somewhat HE 33 [p.1], Oblivious transfer 2 [p.37]
- technique: Bootstrapping 34 [p.3]
- assumption: LWE 55 [p.1], Lattice-based 39 [p.1], IND-CPA 8 [p.11]
- topic: Homomorphic encryption 104 [p.1]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s31-0_efficient-fully-homomorphic-encryption-from-standard-lwe.pdf |
schemes | 38 | 522.2 KB | 8c278ec1f0f0 |
Database key: efficient-fully-homomorphic-encryption-from-standard-lwe · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set efficient-fully-homomorphic-encryption-from-standard-lwe COLUMN VALUE