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