Paillier Cryptosystem
The Paillier cryptosystem is an additively homomorphic public-key encryption scheme introduced by Pascal Paillier in 1999 based on the computational hardness of the composite degree residuosity problem.
Paillier Cryptosystem is an asymmetric public-key encryption scheme in computation and algorithms that provides probabilistic semantic security and an additive homomorphic algebraic structure. Formulated in 1999 by French cryptographer Pascal Paillier, the cryptosystem introduced a solution to the challenge of performing arbitrary linear operations directly on encrypted integer data without requiring decryption, establishing the mathematical foundation for modern privacy-preserving statistical analysis, secure multi-party computation, electronic voting protocols, and federated machine learning.
Within computational complexity theory, the security of the Paillier cryptosystem rests upon the Composite Degree Residuosity Assumption (CDRA). The CDRA asserts that given a composite modulus n = pq and an integer z, it is computationally intractable for any polynomial-time algorithm to decide whether z is an n-th residue modulo n2 (that is, whether there exists an integer y such that z โก yn mod n2) without possessing the prime factorization of n.
Mathematical Architecture and Key Generation
The Paillier cryptosystem operates in the multiplicative group of integers modulo n2, denoted (โค/n2โค)ร.
1. Key Generation Protocol
- Two large, independent prime integers p and q are selected uniformly at random such that gcd(pq, (p โ 1)(q โ 1)) = 1 (a condition naturally satisfied if p and q have equivalent bit lengths).
- The public RSA composite modulus is computed:
n = p ยท q
- The Carmichael function of n is evaluated, representing the exponent of the group (โค/nโค)ร:
lambda = lcm(p โ 1, q โ 1)
- A base generator g โ (โค/n2โค)ร is selected. In simplified implementations, g can be set to n + 1.
- The existence of the modular multiplicative inverse mu is confirmed using the function L(u) = (u โ 1) / n:
mu = (L(glambda mod n2))โ1 mod n
The public key is the pair (n, g), while the private decryption key is the pair (lambda, mu).
Encryption and Decryption Mechanics
Let the plaintext message m be an integer in the message space โคn = {0, 1, ..., n โ 1}.
1. Probabilistic Encryption
To encrypt message m:
- The sender samples a random blinding factor r uniformly from (โค/nโค)ร:
r โ {1, 2, ..., n โ 1} such that gcd(r, n) = 1
- The ciphertext c is computed by combining the base generator raised to the message power with the n-th power of the blinding factor modulo n2:
c = gm ยท rn mod n2
Because the random blinding factor r changes with every encryption call, the scheme is inherently non-deterministic: encrypting the identical message m repeatedly produces uncorrelated ciphertexts in โคn2, satisfying IND-CPA security under the composite degree residuosity assumption.
2. Exact Decryption
To decrypt ciphertext c โ (โค/n2โค)ร using private key (lambda, mu):
- The recipient raises the ciphertext to the private power lambda modulo n2:
clambda โก (gm ยท rn)lambda โก (glambda)m ยท (rlambda)n โก (glambda)m (mod n2)
The term (rlambda)n cancels out completely because Carmichael's theorem guarantees that rlambdaยทn โก 1 (mod n2).
- The plaintext m is extracted using the arithmetic L-function and modular multiplier mu:
m = L(clambda mod n2) ยท mu mod n
Because the L-function involves only elementary integer division by n, decryption requires only a single modular exponentiation modulo n2.
Homomorphic Properties
The defining technological feature of the Paillier cryptosystem is its additive homomorphism: arithmetic operations performed on ciphertexts map directly to linear operations on the underlying decrypted plaintexts.
1. Homomorphic Addition of Plaintexts
Multiplying two ciphertexts c1 and c2 modulo n2 produces a valid ciphertext encrypting the sum of their plaintexts m1 + m2 mod n:
c1 ยท c2 = (gm1 ยท r1n) ยท (gm2 ยท r2n) โก gm1 + m2 ยท (r1 ยท r2)n (mod n2)
Decryption yields:
Dec(c1 ยท c2 mod n2) = m1 + m2 mod n
2. Homomorphic Multiplication by a Known Scalar
Raising a ciphertext c to a plaintext integer scalar k modulo n2 produces a valid ciphertext encrypting the product k ยท m mod n:
ck = (gm ยท rn)k โก gkยทm ยท (rk)n (mod n2)
Decryption yields:
Dec(ck mod n2) = k ยท m mod n
By combining scalar multiplication and ciphertext addition, any client can compute arbitrary linear combinations over encrypted data:
Dec(โ ciwi mod n2) = โ wi ยท mi mod n
Industrial and Scientific Applications
The additive homomorphism of Paillier powers several real-world cryptographic architectures:
- Federated Machine Learning: Multiple decentralized edge devices compute local model gradient updates and encrypt them with the Paillier cryptosystem. A central aggregation server sums the encrypted gradients without decrypting them, computing a global model update without observing any participant's raw training data.
- Privacy-Preserving Electronic Voting: Voters submit encrypted ballots ci = Enc(1) for their preferred candidate. Election auditors multiply all received ciphertexts together modulo n2 to obtain an encryption of the total vote count, which is decrypted in a single operation without exposing individual votes.
- Secure Genomic Processing: Medical databases compute allele frequency statistics across encrypted patient genomes, enabling multi-institutional biomedical research without violating healthcare privacy regulations.
Technical Parameters of Homomorphic Systems
| Parameter | Paillier Cryptosystem | Exponential ElGamal | Fully Homomorphic Encryption (CKKS) |
|---|---|---|---|
| Supported Homomorphic Operations | Addition, Scalar Multiplication | Addition, Scalar Multiplication | Arbitrary Circuits (Add, Mult, Rescale) |
| Plaintext Space | โคn (large integer ring, e.g., 2,048 bits) | โคq (restricted to small ranges) | Complex vector slots (floating-point) |
| Ciphertext Expansion | Exactly 2ร (outputs modulo n2) | Exactly 2ร (two curve points) | Vector polynomials (kilobytes per vector) |
| Decryption Complexity | Single exponentiation modulo n2 | Requires solving discrete logarithm | Polynomial ring operations |
| Post-Quantum Status | Vulnerable to Shor's factoring algorithm | Vulnerable to Shor's algorithm | Lattice-based (quantum resistant) |
References
- Paillier, P. (1999). Public-key cryptosystems based on composite degree residuosity classes. Advances in Cryptology โ EUROCRYPT '99, 223-238.
- Damgรฅrd, I., & Jurik, M. (2001). A generalisation, a simplification and some applications of Paillier's probabilistic public-key system. Public Key Cryptography โ PKC 2001, 119-136.
- Acar, A., Aksu, H., Uluagac, A. S., & Conti, M. (2018). A survey on homomorphic encryption schemes: Theory and implementation. ACM Computing Surveys, 51(4), 1-35.
- Cramer, R., Damgรฅrd, I., & Nielsen, J. B. (2001). Multiparty computation from threshold homomorphic encryption. Advances in Cryptology โ EUROCRYPT 2001, 280-296.