Skip to content

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