Skip to content

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