Skip to content

Public-Key Cryptosystems Based on Composite Degree Residuosity Classes

Authors: Pascal Paillier
Year: 1999
Venue: EUROCRYPT 1999

type: scheme collection: catalogue, schemes status: auto

Links: DOI · link

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