Fully Homomorphic Encryption over the Integers¶
Authors: van Dijk, Gentry, Halevi, Vaikuntanathan
Year: 2010
Venue: EUROCRYPT 2010
type: scheme collection: schemes status: auto
Links: ePrint 2009/616
Visual lesson: DGHV (FHE over the integers) · Scheme table row: DGHV (FHE over the integers)
Summary¶
Auto-extracted summary (unreviewed)
The DGHV paper presents a conceptually simple somewhat-homomorphic encryption scheme that uses only integer addition and multiplication (ciphertext c = pq + 2r + m for a secret odd integer p) and then applies Gentry's squashing and bootstrapping blueprint to obtain a fully homomorphic public-key scheme. Security of the somewhat-homomorphic scheme is reduced to the approximate integer GCD problem, whose hardness the authors analyze building on Howgrave-Graham's work.
Abstract¶
We describe a very simple “somewhat homomorphic” encryption scheme using only elementary modular arithmetic, and use Gentry’s techniques to convert it into a fully homomorphic scheme. Compared to Gentry’s construction, our somewhat homomorphic scheme merely uses addition and multiplication over the integers rather than working with ideal lattices over a polynomial ring. The main appeal of our approach is the conceptual simplicity. We reduce the security of our somewhat homomorphic scheme to finding an approximate integer gcd – i.e., given a list of integers that are near-multiples of a hidden integer, output that hidden integer. We investigate the hardness of this task, building on earlier work of Howgrave- Graham.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | Somewhat homomorphic encryption scheme over the integers using elementary modular arithmetic | llm | 0.90 |
| contribution | Public-key variant via subset sums of encryptions of zero | llm | 0.90 |
| contribution | Conversion to a fully homomorphic scheme by squashing the decryption circuit and bootstrapping | llm | 0.90 |
| contribution | Security reduction to the approximate integer GCD problem and analysis of its hardness | llm | 0.90 |
| schemes | DGHV (integer-based FHE) | llm | 0.90 |
| schemes | approximate GCD | llm | 0.90 |
| tasks | evaluation of boolean circuits on encrypted bits | llm | 0.90 |
| interaction | non-interactive FHE | llm | 0.90 |
| limitations | Efficiency is the primary open problem; the scheme is motivated by conceptual simplicity rather than performance | llm | 0.90 |
| llm relevance | low | llm | 0.90 |
Scheme card: DGHV (FHE over the integers)¶
| Group | 5. Earlier and other FHE constructions |
| Kind | Scheme |
| Hardness assumption | Approximate GCD |
| Plaintext type | Bits |
| SIMD packing | Limited (later batch variants) |
| Bootstrapping | Yes |
| Post-quantum | Yes |
| Status | Foundational |
| Fit for LLM inference | Conceptually simple but has large keys. Not used for ML. |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: Leveled / somewhat HE 13 [p.1], RSA 6 [p.8], Garbled circuits 3 [p.4], PIR 2 [p.20]
- technique: Bootstrapping 14 [p.2]
- assumption: Lattice-based 34 [p.1]
- topic: Homomorphic encryption 17 [p.2]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s29-0_fully-homomorphic-encryption-over-the-integers.pdf |
schemes | 28 | 358.4 KB | 7fb2e597a7b3 |
Database key: fully-homomorphic-encryption-over-the-integers · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set fully-homomorphic-encryption-over-the-integers COLUMN VALUE