Paillier cryptosystem

The Paillier cryptosystem is an asymmetric algorithm for public key cryptography, invented by Pascal Paillier in 1999. It 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 <math>\phi=(p-1)(q-1)<math>
3. The public key is N and the private key is <math>\phi<math>

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:

<math> c=(1+N)^m \cdot r^N \mod N^2 <math>

Decryption

To recover the plaintext m, observe that:

<math> c=r^N \mod N <math>

and

<math> (1+N)^m=1+m \cdot N=\frac{c}{r^N} \mod N^2 <math>

Therefore compute:

<math> r=c^{N^{-1} \mod \phi} \mod N <math>

<math> m=\frac{(c \cdot r^{-N} \mod N^2) -1}{N} <math>