Skip to content

Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based

Authors: Gentry, Sahai, Waters
Year: 2013
Venue: CRYPTO 2013

type: scheme collection: catalogue, schemes status: auto

Links: ePrint 2013/340

Visual lesson: GSW · Scheme table row: GSW

Summary

Auto-extracted summary (unreviewed)

Gentry, Sahai and Waters present the GSW fully homomorphic encryption scheme from LWE using an approximate eigenvector method, in which homomorphic addition and multiplication are essentially matrix addition and multiplication, removing the expensive relinearization step and the need for an evaluation key. Since the evaluator needs no public key beyond basic parameters, the technique yields the first identity-based FHE scheme and, by compiling the Gorbunov et al. attribute-based encryption for circuits, an attribute-based FHE scheme; the construction is asymptotically faster and conceptually simpler than prior LWE-based FHE.

Abstract

We describe a comparatively simple fully homomorphic encryption (FHE) scheme based on the learning with errors (LWE) problem. In previous LWE-based FHE schemes, multiplication is a complicated and expensive step involving “relinearization”. In this work, we propose a new technique for building FHE schemes that we call the approximate eigenvector method. In our scheme, for the most part, homomorphic addition and multiplication are just matrix addition and multiplication. This makes our scheme both asymptotically faster and (we believe) easier to understand. In previous schemes, the homomorphic evaluator needs to obtain the user’s “evaluation key”, which consists of a chain of encrypted secret keys. Our scheme has no evaluation key. The evaluator can do homomorphic operations without knowing the user’s public key at all, except for some basic parameters. This fact helps us construct the first identity-based FHE scheme. Using similar techniques, we show how to compile a recent attribute-based encryption scheme for circuits by Gorbunov et al. into an attribute-based FHE scheme that permits data encrypted under the same index to be processed homomorphically.
Source: pdf

Extracted details

Field Value Source Confidence
contribution approximate eigenvector method for LWE-based FHE llm 0.85
contribution homomorphic operations as matrix addition and multiplication without relinearization or evaluation keys llm 0.85
contribution first identity-based FHE scheme llm 0.85
contribution attribute-based FHE from the Gorbunov et al. ABE for circuits llm 0.85
schemes GSW llm 0.85
schemes LWE llm 0.85
schemes RLWE llm 0.85
tasks fully homomorphic encryption construction llm 0.85
tasks identity-based and attribute-based homomorphic encryption llm 0.85
interaction non-interactive FHE llm 0.85
llm relevance low llm 0.85

Scheme card: GSW

Group 3. Bit-wise / lookup-table FHE (GSW, FHEW, TFHE family)
Kind Scheme
Hardness assumption LWE
Plaintext type Bits / small integers
SIMD packing No
Bootstrapping Yes (via AP14)
Post-quantum Yes
Status Foundational
Fit for LLM inference Basis of blind rotation in FHEW/TFHE. Not used directly for ML.
Follow-ups Faster bootstrapping with polynomial error (Alperin-Sheriff–Peikert, 2014/094); CCA1-secure GG-GSW (2026/316).
Follow-up papers in the archive Faster bootstrapping with polynomial error
GG-GSW: Chosen-Ciphertext Secure Leveled FHE From Gadget Trapdoors

System card: GSW

Group 4. Alternative FHE schemes
Family LWE, matrix ciphertexts
Arithmetic Bits / small integers
Interaction Non-interactive
Model scale -
Status Foundational
Relation to the SoK Basis of FHEW/TFHE blind rotation.
Note Slow noise growth for multiplication by bits. Used as the accumulator in modern bootstrapping.
Systems page GSW

Keyword mentions

Counts of vocabulary terms in the full text (first page of occurrence in brackets).

  • scheme: Leveled / somewhat HE 14 [p.2]
  • technique: Relinearization 19 [p.1], Compiler 19 [p.3], Bootstrapping 15 [p.2], Modulus switching 3 [p.3], Matrix multiplication 3 [p.3]
  • assumption: LWE 76 [p.1], RLWE 23 [p.3], Lattice-based 20 [p.7]
  • topic: Homomorphic encryption 103 [p.1]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/catalogue/4-052_homomorphic-encryption-from-learning-with-errors-conceptuall.pdf catalogue 25 412.4 KB 8edb94cfd852
references/schemes/s20-0_homomorphic-encryption-from-learning-with-errors-conceptuall.pdf schemes 25 412.4 KB 8edb94cfd852 byte-identical to references/catalogue/4-052_homomorphic-encryption-from-learning-with-errors-conceptuall.pdf

Database key: homomorphic-encryption-from-learning-with-errors-conceptually-simpler · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set homomorphic-encryption-from-learning-with-errors-conceptually-simpler COLUMN VALUE