Public-Key Cryptosystems Based on Composite Degree Residuosity Classes¶
Authors: Pascal Paillier
Year: 1999
Venue: EUROCRYPT 1999
type: scheme collection: catalogue, schemes status: auto
Visual lesson: Paillier · Scheme table row: Paillier
Summary¶
Auto-extracted summary (unreviewed)
Paillier introduces the Composite Residuosity Class Problem over Z*_{n^2} with n = pq and builds a new trapdoor mechanism from it, deriving a trapdoor permutation and two homomorphic probabilistic encryption schemes with cost comparable to RSA. The schemes rely on ordinary modular arithmetic and are provably secure under the stated residuosity assumptions in the standard model, providing the additively homomorphic cryptosystem now known as Paillier encryption.
Abstract¶
This paper investigates a novel computational problem, namely the Composite Residuosity Class Problem, and its applications to public-key cryptography. We propose a new trapdoor mechanism and derive from this technique three encryption schemes : a trapdoor permutation and two homomorphic probabilistic encryption schemes computationally comparable to RSA. Our cryptosystems, based on usual modular arithmetics, are provably secure under appropriate assumptions in the standard model. 1 Background Since the discovery of public-key cryptography by Diffie and Hellman [5], very few convincingly secure asymetric schemes have been discovered despite considerable research efforts. We refer the reader to [26] for a thorough survey of existing public-key cryptosystems. Basically, two major species of trapdoor techniques are in use today. The first points to RSA [25] and related variants such as Rabin-Williams [24,30], LUC, Dickson’s scheme or elliptic curve versions of RSA like KMOV [10]. The technique conjugates the polynomial-time extraction of roots of polynomials over a finite field with the intractability of factoring large numbers. It is worthwhile pointing out that among cryptosystems belonging to this family, only Rabin- Williams has been proven equivalent to the factoring problem so far. Another famous technique, related to Diffie-Hellman-type schemes (El Gamal [7], DSA, McCurley [14], etc.) combines the homomorphic properties of the modular exponentiation and the intractability of extracting discrete logarithms over finite groups. Again, equivalence with the primitive computational problem remains open in general, unless particular circumstances are reached as described in [12]. Other proposed mechanisms generally suffer from inefficiency, inherent security weaknesses or insufficient public scrutiny : McEliece’s cryptosystem [15] J. Stern (Ed.): EUROCRYPT’99, LNCS 1592, pp. 223–238, 1999. c ⃝Springer-Verlag Berlin Heidelberg 1999 224 Pascal Paillier based on error correcting codes, Ajtai-Dwork’s scheme based on lattice problems (cryptanalyzed by Nguyen and Stern in [18]), additive and multiplicative knapsack-type systems including Merkle-Hellman [13], Chor-Rivest (broken by Vaudenay in [29]) and Naccache-Stern [17] ; finally, Matsumoto-Imai and Goubin-Patarin cryptosystems, based on multivariate polynomials, were successively cryptanalyzed in [11] and [21]. We believe, however, that the cryptographic research had unnoticeably witnessed the progressi
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | Composite Residuosity Class Problem as a new computational assumption | llm | 0.85 |
| contribution | new trapdoor mechanism based on composite-degree residuosity classes | llm | 0.85 |
| contribution | trapdoor permutation and two additively homomorphic probabilistic encryption schemes computationally comparable to RSA | llm | 0.85 |
| contribution | provable security in the standard model under appropriate assumptions | llm | 0.85 |
| schemes | Paillier | llm | 0.85 |
| llm relevance | low | llm | 0.85 |
Scheme card: Paillier¶
| Group | 8. Partially homomorphic encryption |
| Kind | Scheme |
| Hardness assumption | Decisional composite residuosity |
| Plaintext type | Integers mod n, additions only |
| SIMD packing | No |
| Bootstrapping | n/a (no multiplication) |
| Post-quantum | No |
| Status | Widely used |
| Fit for LLM inference | Only linear operations on encrypted data. Used for secure aggregation, not full Transformers. |
| Follow-ups | Damgård–Jurik generalization (PKC 2001). |
| Libraries | python-paillier |
System card: Paillier (partially HE)¶
| Group | 4. Alternative FHE schemes |
| Family | Additive partially homomorphic |
| Arithmetic | Exact integers, additions only |
| Interaction | Non-interactive for linear ops |
| Model scale | Linear models |
| Status | Foundational |
| Relation to the SoK | Supports only addition, no multiplication of ciphertexts. |
| Note | Used in early PPML and federated aggregation. Cannot evaluate Transformers alone. |
| Code | https://github.com/data61/python-paillier |
| Systems page | Paillier (partially HE) |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: RSA 21 [p.1], Paillier 9 [p.1], ElGamal 4 [p.1]
- assumption: Composite residuosity 15 [p.1]
- topic: Homomorphic encryption 2 [p.2]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/4-047_public-key-cryptosystems-based-on-composite-degree-residuosi.pdf |
catalogue | 16 | 291.5 KB | bc5e3cec2ff4 |
|
references/schemes/s43-0_public-key-cryptosystems-based-on-composite-degree-residuosi.pdf |
schemes | 16 | 291.5 KB | bc5e3cec2ff4 |
byte-identical to references/catalogue/4-047_public-key-cryptosystems-based-on-composite-degree-residuosi.pdf |
Database key: public-key-cryptosystems-based-on-composite-degree-residuosity-classes · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set public-key-cryptosystems-based-on-composite-degree-residuosity-classes COLUMN VALUE