โ† Wiki Index / Computation & Algorithms / Paillier Cryptosystem
๐Ÿ’ป Computation & Algorithms

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

  1. 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).
  2. The public RSA composite modulus is computed:

n = p ยท q

  1. The Carmichael function of n is evaluated, representing the exponent of the group (โ„ค/nโ„ค)ร—:

lambda = lcm(p โˆ’ 1, q โˆ’ 1)

  1. A base generator g โˆˆ (โ„ค/n2โ„ค)ร— is selected. In simplified implementations, g can be set to n + 1.
  2. 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:

  1. The sender samples a random blinding factor r uniformly from (โ„ค/nโ„ค)ร—:

r โˆˆ {1, 2, ..., n โˆ’ 1} such that gcd(r, n) = 1

  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):

  1. 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).

  1. 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

ParameterPaillier CryptosystemExponential ElGamalFully Homomorphic Encryption (CKKS)
Supported Homomorphic OperationsAddition, Scalar MultiplicationAddition, Scalar MultiplicationArbitrary 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 ExpansionExactly 2ร— (outputs modulo n2)Exactly 2ร— (two curve points)Vector polynomials (kilobytes per vector)
Decryption ComplexitySingle exponentiation modulo n2Requires solving discrete logarithmPolynomial ring operations
Post-Quantum StatusVulnerable to Shor's factoring algorithmVulnerable to Shor's algorithmLattice-based (quantum resistant)

References

  1. Paillier, P. (1999). Public-key cryptosystems based on composite degree residuosity classes. Advances in Cryptology โ€” EUROCRYPT '99, 223-238.
  2. 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.
  3. 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.
  4. Cramer, R., Damgรฅrd, I., & Nielsen, J. B. (2001). Multiparty computation from threshold homomorphic encryption. Advances in Cryptology โ€” EUROCRYPT 2001, 280-296.
๐Ÿงฌ Support Open Science
Explore interactive science games on LowKey Games or browse scientific apparel & accessories in the CRV Science Shop.
๐Ÿ’ก Spot an inaccuracy or have primary literature to expand this article?
Submit a citation or revision note using your shared CRV Science / LowKey Games profile ID.
Suggest Revision