Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes¶
Authors: Smart, Vercauteren
Year: 2010
Venue: PKC 2010
type: scheme collection: schemes status: auto
Links: ePrint 2009/571
Visual lesson: Smart–Vercauteren (SIMD FHE) · Scheme table row: Smart–Vercauteren (SIMD FHE)
Summary¶
Auto-extracted summary (unreviewed)
Smart and Vercauteren give a Gentry-style FHE construction, described with elementary algebraic number theory, in which the public key is a prime p and an integer alpha mod p, the secret key is an integer (or integer polynomial), and a ciphertext is a single integer modulo p, giving much smaller keys and message expansion than Gentry's scheme and supporting any field of characteristic two. An NTL implementation of the somewhat-homomorphic scheme shows encryption and multiplication in milliseconds for N up to 2^11, but key generation takes hours and, at practical parameters, the achievable multiplicative depth is too small to make the scheme fully homomorphic.
Abstract¶
We present a fully homomorphic encryption scheme which has both relatively small key and ciphertext size. Our construction follows that of Gentry by producing a fully homomorphic scheme from a “somewhat” homomorphic scheme. For the somewhat homomorphic scheme the public and private keys consist of two large integers (one of which is shared by both the public and private key) and the ciphertext consists of one large integer. As such, our scheme has smaller message expansion and key size than Gentry’s original scheme. In addition, our proposal allows efficient fully homomorphic encryption over any field of characteristic two.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | Somewhat homomorphic scheme over principal ideal lattices with public key (p, alpha) and single-integer ciphertexts | llm | 0.85 |
| contribution | Smaller key and ciphertext sizes than Gentry's original scheme | llm | 0.85 |
| contribution | Fully homomorphic conversion via Gentry's recrypt / squashing approach | llm | 0.85 |
| contribution | Support for encrypting binary polynomials, i.e. efficient FHE over fields of characteristic two | llm | 0.85 |
| contribution | Parameter and security analysis with an NTL-based implementation of the somewhat-homomorphic scheme | llm | 0.85 |
| schemes | Smart-Vercauteren (principal ideal lattice FHE) | llm | 0.85 |
| schemes | Gentry's bootstrapping | llm | 0.85 |
| libraries | NTL | llm | 0.85 |
| tasks | evaluation of boolean circuits / binary polynomials on encrypted data | llm | 0.85 |
| hardware | 2.4 GHz Intel Core2 6600, x86-64 | llm | 0.85 |
| security level | assumed 2^(N/epsilon), e.g. about 2^54 to 2^100 for n = 11 to 13 with mu = 2 | llm | 0.85 |
| interaction | non-interactive FHE | llm | 0.85 |
| limitations | For practical values of n the scheme cannot be made fully homomorphic because the required recrypt depth exceeds the achievable depth; fully homomorphic only for n >= 27 asymptotically | llm | 0.85 |
| limitations | Key generation could take many hours and was not possible for N = 2^12 on the test machine | llm | 0.85 |
| limitations | Security and depth estimates are described as very crude | llm | 0.85 |
| llm relevance | low | llm | 0.85 |
| key result | encryption time: 4.2 ms (n=8) to 3717 ms (n=11) (somewhat homomorphic scheme, NTL, 2.4 GHz Core2) | llm | 0.85 |
| key result | decryption time: 0.2 ms (n=8) to 3.0 ms (n=11) (somewhat homomorphic scheme) | llm | 0.85 |
| key result | multiplication time: 0.2 ms (n=8) to 1.6 ms (n=11) (somewhat homomorphic scheme) | llm | 0.85 |
| key result | achieved multiplicative depth: 1.0 to 2.5 (mu = 2) in practice (required depth for bootstrapping estimated at 7-8) | llm | 0.85 |
Scheme card: Smart–Vercauteren (SIMD FHE)¶
| Group | 5. Earlier and other FHE constructions |
| Kind | Scheme |
| Hardness assumption | Principal ideal lattices |
| Plaintext type | Bits / small field elements |
| SIMD packing | Yes (first SIMD packing) |
| Bootstrapping | Yes |
| Post-quantum | No (later attacks on principal ideals) |
| Status | Foundational |
| Fit for LLM inference | Introduced the SIMD slot packing that CKKS relies on. |
| Follow-ups | Fully homomorphic SIMD operations (2011/133). |
| Follow-up papers in the archive | Fully Homomorphic SIMD Operations |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: Leveled / somewhat HE 16 [p.1], NTRU 2 [p.1]
- assumption: Lattice-based 24 [p.1]
- topic: Homomorphic encryption 13 [p.1]
Related papers¶
- Fully Homomorphic SIMD Operations follow up of this paper — follow-up listed for scheme "Smart–Vercauteren (SIMD FHE)"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s30-0_fully-homomorphic-encryption-with-relatively-small-key-and-c.pdf |
schemes | 19 | 262.5 KB | 246485d72a8f |
Database key: fully-homomorphic-encryption-with-relatively-small-key-and-ciphertext · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set fully-homomorphic-encryption-with-relatively-small-key-and-ciphertext COLUMN VALUE