The Paillier Cryptosystem

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 one specific mathematical operation, addition, directly on encrypted values without ever decrypting them. You still 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
• Python Implementation
• Limitations
• 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. The operation never touches 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 is 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. Most importantly, it 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. This works 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. 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

Python Implementation

This is a genuine, complete implementation of key generation, encryption, decryption, and the homomorphic addition trick, using the same small demonstration primes as the worked example above:

import math
import random

def L(x: int, n: int) -> int:
    return (x - 1) // n

def generate_keypair(p: int, q: int):
    n = p * q
    g = n + 1
    lam = (p - 1) * (q - 1) // math.gcd(p - 1, q - 1)  # lcm(p-1, q-1)
    mu = pow(lam, -1, n)
    return (n, g), (lam, mu)

def encrypt(m: int, public_key) -> int:
    n, g = public_key
    n2 = n * n
    while True:
        r = random.randrange(1, n)
        if math.gcd(r, n) == 1:
            break
    return (pow(g, m, n2) * pow(r, n, n2)) % n2

def decrypt(c: int, private_key, n: int) -> int:
    lam, mu = private_key
    n2 = n * n
    return (L(pow(c, lam, n2), n) * mu) % n

if __name__ == "__main__":
    p, q = 7, 11
    public_key, private_key = generate_keypair(p, q)
    n, g = public_key
    print(f"n={n}, g={g}, lambda={private_key[0]}, mu={private_key[1]}")

    c1 = encrypt(15, public_key)
    c2 = encrypt(40, public_key)

    c_sum = (c1 * c2) % (n * n)  # homomorphic addition: multiply the ciphertexts
    result = decrypt(c_sum, private_key, n)

    print(f"Decrypted sum: {result}")

Running this reproduces the worked example above exactly: n=77, g=78, lambda=30, mu=18, and multiplying the two ciphertexts together and decrypting the result yields 55, the same as 15 + 40 mod 77, with the individual values never decrypted along the way.

Limitations

This is a genuine, complete implementation of the real algorithm, not a simplified stand-in:

• Toy-sized primes. Real Paillier needs primes matching RSA’s modern key-size recommendations (see the Security Considerations section below); p=7, q=11 here are trivially factorable, chosen purely to keep the arithmetic checkable by hand.
• No input validation. encrypt doesn’t check that 0 <= m < n, and decrypt doesn’t validate that c is actually a valid ciphertext under this key; a real implementation would need both.
• random.randrange isn’t cryptographically secure. Python’s random module is a Mersenne Twister PRNG, not suitable for generating the blinding factor r in a real deployment; that should come from secrets.randbelow or an equivalent CSPRNG.
• Never use this, or hand-rolled Paillier of any size, in production. Real applications should use a vetted library (such as phe, the Python Paillier library from the OpenMined project) for actual homomorphic encryption.

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. Critically, it also requires 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. That’s 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. It’s less universally deployed than RSA or AES, though, 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. Paillier’s ciphertexts are also 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.