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]
Related papers¶
- Faster bootstrapping with polynomial error follow up of this paper — follow-up listed for scheme "GSW"
- GG-GSW: Chosen-Ciphertext Secure Leveled FHE From Gadget Trapdoors follow up of this paper — follow-up listed for scheme "GSW"
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