Paillier cryptosystem

The Paillier cryptosystem is an asymmetric algorithm for public key cryptography, invented by Pascal Paillier in 1999.

The scheme is an additive homomorphic cryptosystem; this means that, given only the public-key and the encryption of m₁ and m₂, one can compute the encryption of m₁ + m₂.

The encryption scheme works as follows:

Key generation

1. Choose two large prime numbers p and q randomly and independently of each other.
2. Compute N=pq and φ = (p - 1)(q - 1)
3. The public key is N and the private key is φ

Encryption

Let m be a message to be encrypted, with 0<m<N. Let r be some random integer between 0 and N. The ciphertext is:

Decryption

To recover the plaintext m, observe that:

and

Therefore compute:

References

• Pascal Paillier, Public-Key Cryptosystems Based on Composite Degree Residuosity Classes, EUROCRYPT 1999, pp223-238.