The Paillier Cryptosystem

Introduction

Every cryptosystem covered elsewhere on this site treats ciphertext as something you must decrypt before you can do anything useful with it. Pascal Paillier’s 1999 cryptosystem breaks that pattern: it’s partially homomorphic, meaning you can perform a specific mathematical operation — addition — directly on encrypted values, without ever decrypting them, and get a result that decrypts to the correct sum. This single property makes Paillier a foundational building block for privacy-preserving technologies: secure electronic voting, private data aggregation, and secure multi-party computation.

Table of Contents

• What Does “Homomorphic” Mean?
• Key Generation
• Encryption and Decryption
• The Homomorphic Addition Property
• A Worked Example
• Real-World Applications
• Security Considerations
• FAQ
• References

What Does “Homomorphic” Mean?

A homomorphic encryption scheme has the property that some mathematical operation on ciphertexts corresponds directly to a related operation on the underlying plaintexts. Paillier is specifically additively homomorphic: multiplying two Paillier ciphertexts together (under the encryption scheme’s modular arithmetic) produces a new ciphertext that decrypts to the sum of the two original plaintexts — without the operation ever touching the actual unencrypted numbers. (Fully homomorphic encryption, supporting arbitrary computation on encrypted data, is a much newer and more complex research area; Paillier predates it by over a decade and supports just this one operation, which turns out to be extremely useful on its own.)

Key Generation

1. Choose two large primes, p and q (similar to RSA), and compute the modulus n = p × q.
2. Set g = n + 1 — a valid, simple choice that satisfies Paillier’s mathematical requirements (the original paper allows other choices of g, but n+1 is the standard simplification used almost everywhere in practice).
3. Compute λ = lcm(p − 1, q − 1) (the Carmichael function of n).
4. Compute μ = λ⁻¹ mod n (the modular inverse of λ).
5. The public key is (n, g). The private key is (λ, μ).

Encryption and Decryption

To encrypt a message m (an integer, 0 ≤ m < n), choose a random r coprime to n, then compute:

C = gᵐ · rⁿ mod n²

Note the ciphertext lives in the much larger ring of integers mod n², not mod n — this extra room is exactly what makes the homomorphic addition trick work.

To decrypt, using the private key (λ, μ):

M = L(Cλ mod n²) · μ mod n

where L(x) = (x − 1) / n — a specific function defined so its output is always an exact integer for the values it’s applied to in this scheme.

Interactive Visualizer

The visualizer above runs genuine Paillier key generation, encryption, and decryption with small demonstration primes, and — most importantly — lets you encrypt two separate numbers, multiply their ciphertexts together, and decrypt the result to see the sum appear, all without ever decrypting the individual values along the way.

The Homomorphic Addition Property

Given two ciphertexts C₁ = Encrypt(m₁, r₁) and C₂ = Encrypt(m₂, r₂), computing:

C₁ · C₂ mod n²

produces a new valid ciphertext that decrypts to (m₁ + m₂) mod n — as if you’d encrypted the sum directly, despite never having access to m₁ or m₂ individually. This isn’t a coincidence; it falls directly out of the exponent arithmetic in the encryption formula: multiplying gᵐ¹ by gᵐ² gives g^(m₁+m₂), exactly as ordinary exponent rules would predict, while the random blinding factors rⁿ combine harmlessly in the same multiplication.

A Worked Example

Using small demonstration primes:

• Primes: p = 7, q = 11 → n = 77, g = 78
• Private key: λ = 30, μ = 18
• Encrypting m₁ = 15 and m₂ = 40 produces two ciphertexts
• Multiplying those ciphertexts together (mod n²) and decrypting the result yields 55 — exactly 15 + 40 mod 77 — without the sum ever having been computed on unencrypted data

Real-World Applications

• Electronic voting: individual encrypted votes can be homomorphically summed into an encrypted tally, which is only decrypted once, at the very end — no single vote is ever individually decrypted or exposed.
• Private data aggregation: smart meters, medical research, and financial reporting systems can submit encrypted individual readings that get summed (or averaged) without any party seeing individual data points.
• Secure multi-party computation: Paillier is a common building block in larger cryptographic protocols where multiple parties need to jointly compute something (like a sum or average) without revealing their individual inputs to each other.

Security Considerations

Paillier’s security rests on the decisional composite residuosity assumption — a problem believed to be as hard as factoring n, similar in spirit to RSA’s security foundation. Like RSA, it requires sufficiently large primes (matching RSA’s modern key-size recommendations) to resist factoring attacks, and — critically — a fresh random r for every single encryption, since reusing r values (or using predictable ones) can leak information about the plaintexts.

FAQ

Is Paillier the same as fully homomorphic encryption (FHE)?

No — Paillier is partially homomorphic, supporting only addition (and, as a consequence, multiplication of a ciphertext by a known plaintext constant). Fully homomorphic encryption, which supports arbitrary computation on encrypted data, is a separate and much more computationally expensive area of cryptography developed starting around 2009.

Why does Paillier need such large ciphertexts (working mod n²)?

The extra “room” in n² compared to n is exactly what allows the ciphertext multiplication trick to correctly encode plaintext addition — a mathematical necessity of how the encryption function is constructed, not an implementation inefficiency.

Can Paillier multiply two encrypted numbers together?

Not directly between two ciphertexts — only addition (via ciphertext multiplication) and multiplying a ciphertext by a known, unencrypted constant are supported natively. Multiplying two encrypted unknowns together requires more advanced techniques beyond plain Paillier.

Is Paillier used in real production systems today?

Yes, particularly in privacy-focused voting systems and secure aggregation protocols, though it’s less universally deployed than RSA or AES since its use case (homomorphic computation) is more specialized than general-purpose encryption.

How is Paillier different from RSA?

Both rely on the difficulty of factoring a composite modulus n = p×q, but RSA is not homomorphic in the additive sense Paillier is (RSA has a limited multiplicative homomorphic property instead), and Paillier’s ciphertexts are deliberately randomized (via r) so the same plaintext never produces the same ciphertext twice — unlike textbook RSA.

References

1. Paillier, P. “Public-Key Cryptosystems Based on Composite Degree Residuosity Classes.” EUROCRYPT 1999 — the original paper.

2. Wikipedia. “Paillier cryptosystem.” Available at: https://en.wikipedia.org/wiki/Paillier_cryptosystem

3. Damgård, I. and Jurik, M. “A Generalisation, a Simplification and Some Applications of Paillier’s Probabilistic Public-Key System.” PKC 2001.

4. Adida, B. “Helios: Web-based Open-Audit Voting.” USENIX Security 2008 — an example real-world voting system using homomorphic tallying.