Skip to content

Linearly Homomorphic Encryption from DDH

Authors: Castagnos, Laguillaumie
Year: 2015
Venue: CT-RSA 2015

type: scheme collection: schemes status: auto

Links: ePrint 2015/47 · link

Visual lesson: Castagnos–Laguillaumie (class groups) · Scheme table row: Castagnos–Laguillaumie (class groups)

Summary

Auto-extracted summary (unreviewed)

Castagnos and Laguillaumie give the first linearly (additively) homomorphic encryption scheme whose security rests solely on a decisional Diffie-Hellman-type assumption, instantiated in the class group of a non-maximal order of an imaginary quadratic field, where the group order is unknown but a subgroup with easy discrete logarithms exists. The message space is all of Z/pZ with unbounded additions mod p, and because security no longer depends on factoring, the prime p can be sized independently of the security level; timings show the scheme is competitive with Paillier (e.g., 82 ms encryption / 45 ms decryption for the fast variant with 1348-bit discriminant versus 28 / 28 ms for 2048-bit Paillier).

Abstract

We design a linearly homomorphic encryption scheme whose security relies on the hardness of the decisional Diffie-Hellman problem. Our approach requires some special features of the underlying group. In particular, its order is unknown and it contains a subgroup in which the discrete logarithm problem is tractable. Therefore, our instantiation holds in the class group of a non maximal order of an imaginary quadratic field. Its algebraic structure makes it possible to obtain such a linearly homomorphic scheme whose message space is the whole set of integers modulo a prime p and which supports an unbounded number of additions modulo p from the ciphertexts. A notable difference with previous works is that, for the first time, the security does not depend on the hardness of the factorization of integers. As a consequence, under some conditions, the prime p can be scaled to fit the application needs.
Source: pdf

Extracted details

Field Value Source Confidence
contribution First linearly homomorphic encryption secure under a DDH-like assumption llm 0.80
contribution Instantiation in class groups of non-maximal orders of imaginary quadratic fields llm 0.80
contribution Message space Z/pZ with p chosen independently of the security parameter llm 0.80
contribution Faster variant and efficiency comparison against Paillier and BCP03 llm 0.80
schemes CL linearly homomorphic encryption (class group, DDH) llm 0.80
tasks additively homomorphic encryption llm 0.80
tasks e-voting (motivating application) llm 0.80
security level 1348-bit and 1828-bit discriminants, compared against 2048-bit and 3072-bit Paillier moduli llm 0.80
interaction other llm 0.80
limitations Requires a group of unknown order containing a subgroup with tractable discrete logarithms llm 0.80
limitations Restrictions on the choice of the message prime p in some variants llm 0.80
llm relevance low llm 0.80
key result encryption / decryption time: 93 ms / 49 ms (new proposal, 1348-bit discriminant, 80-bit messages) llm 0.80
key result encryption / decryption time: 82 ms / 45 ms (variant of Subsec. 4.2, 1348-bit discriminant, 80-bit messages) llm 0.80
key result encryption / decryption time (baseline): 28 ms / 28 ms (Paillier, 2048-bit modulus, 2048-bit messages) llm 0.80
key result encryption / decryption time: 145 ms / 78 ms (variant of Subsec. 4.2, 1828-bit discriminant, 80-bit messages (Paillier 3072-bit: 109 / 109 ms)) llm 0.80

Scheme card: Castagnos–Laguillaumie (class groups)

Group 8. Partially homomorphic encryption
Kind Scheme
Hardness assumption DDH in class groups
Plaintext type Integers mod a prime, additions
SIMD packing No
Bootstrapping n/a
Post-quantum No
Status Niche
Fit for LLM inference Additive HE with flexible prime message space. Used in threshold ECDSA and MPC.

Keyword mentions

Counts of vocabulary terms in the full text (first page of occurrence in brackets).

  • scheme: Paillier 20 [p.2], RSA 8 [p.2]
  • assumption: DDH 47 [p.1], Lattice-based 2 [p.2]
  • topic: Homomorphic encryption 21 [p.1]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/schemes/s49-0_linearly-homomorphic-encryption-from-ddh.pdf schemes 23 450.6 KB f26e73f64de2

Database key: linearly-homomorphic-encryption-from-ddh · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set linearly-homomorphic-encryption-from-ddh COLUMN VALUE