Skip to content

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]

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