A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System¶
Authors: Ivan Damgård; Mads Jurik
Year: 2001
Venue: PKC 2001
type: scheme collection: schemes status: auto
Links: DOI
Visual lesson: Damgård–Jurik · Scheme table row: Damgård–Jurik
Summary¶
Auto-extracted summary (unreviewed)
Damgard and Jurik generalise Paillier's cryptosystem to computations modulo n^(s+1), which cuts the ciphertext expansion factor from 2 to almost 1, lets the block length be chosen per encryption after the public key is fixed, and simplifies the public key to just the modulus n, all while keeping the additive homomorphism and provably the same security as Paillier. They add a threshold decryption variant (proved secure in the random oracle model) and zero-knowledge protocols for proving that a ciphertext encrypts one of a set of plaintexts or satisfies multiplicative relations. These building blocks yield electronic-voting schemes (yes/no, t-out-of-L, receipt-free) that drastically reduce tallying work, with ballots of only O(log L) bits for 1-out-of-L elections in a certain parameter range.
Abstract¶
We propose a generalisation of Paillier’s probabilistic public key system, in which the expansion factor is reduced and which allows to adjust the block length of the scheme even after the public key has been fixed, without loosing the homomorphic property. We show that the generalisation is as secure as Paillier’s original system. We construct a threshold variant of the generalised scheme as well as zero-knowledge protocols to show that a given ciphertext encrypts one of a set of given plaintexts, and protocols to verify multiplicative relations on plaintexts. We then show how these building blocks can be used for applying the scheme to efficient electronic voting. This reduces dramatically the work needed to compute the final result of an election, compared to the previously best known schemes. We show how the basic scheme for a yes/no vote can be easily adapted to casting a vote for up to t out of L candidates. The same basic building blocks can also be adapted to provide receipt-free elections, under appropriate physical assumptions. The scheme for 1 out of L elections can be optimised such that for a certain range of parameter values, a ballot has size only O(log L) bits.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | generalisation of Paillier encryption to modulus n^(s+1) with expansion factor close to 1 | llm | 0.85 |
| contribution | simplified public key consisting only of the modulus n, with adjustable block length | llm | 0.85 |
| contribution | proof that the generalisation is as secure as Paillier's original scheme | llm | 0.85 |
| contribution | threshold variant of the generalised scheme secure in the random oracle model | llm | 0.85 |
| contribution | zero-knowledge proofs for plaintext membership and multiplicative relations | llm | 0.85 |
| contribution | efficient electronic voting schemes including t-out-of-L and receipt-free variants | llm | 0.85 |
| schemes | Paillier | llm | 0.85 |
| schemes | Damgard-Jurik (generalised Paillier) | llm | 0.85 |
| schemes | threshold decryption | llm | 0.85 |
| schemes | zero-knowledge proofs | llm | 0.85 |
| tasks | electronic voting | llm | 0.85 |
| threat model | threshold servers (any large enough subset can decrypt), random oracle model | llm | 0.85 |
| interaction | other | llm | 0.85 |
| key result | ciphertext expansion factor: almost 1 (vs 2 for Paillier) (generalised scheme modulo n^(s+1)) | llm | 0.85 |
| key result | ballot size: O(log L) bits (optimised 1-out-of-L election, certain parameter range) | llm | 0.85 |
Scheme card: Damgård–Jurik¶
| Group | 8. Partially homomorphic encryption |
| Kind | Scheme |
| Hardness assumption | Decisional composite residuosity |
| Plaintext type | Integers mod n^s, additions |
| SIMD packing | No |
| Bootstrapping | n/a |
| Post-quantum | No |
| Status | Niche |
| Fit for LLM inference | Larger plaintext space than Paillier. Used in voting and threshold settings. |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: Paillier 35 [p.1], Zero-knowledge proofs 12 [p.1], RSA 11 [p.1], MPC 3 [p.10], Secret sharing 2 [p.9]
- technique: Non-interactive 3 [p.10]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s44-0_a-generalisation-a-simplification-and-some-applications-of-p.pdf |
schemes | 18 | 244.7 KB | d49589b68bb9 |
Database key: a-generalisation-a-simplification-and-some-applications-of-paillier-s · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set a-generalisation-a-simplification-and-some-applications-of-paillier-s COLUMN VALUE