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 <math>m_1<math> and <math>m_2<math>, one can compute the encryption of <math>m_1+m_2<math>.
The encryption scheme works as follows:
| Contents |
Key generation
- Choose two large prime numbers p and q randomly and independently of each other.
- Compute N=pq and <math>\phi=(p-1)(q-1)<math>
- 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 \equiv 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>
References
- Pascal Paillier, Public-Key Cryptosystems Based on Composite Degree Residuosity Classes, EUROCRYPT 1999, pp223-238.