Paillier encryption

The Paillier encryption is a public-key encryption scheme based on the decisional composite residuosity assumption. ECLib implements the following algorithms.

Key generation

The key generation algorithm takes a key length \(k\) as input and outputs public parameters \(n\), public key \(g\), and secret key \((\lambda, \mu)\), where \(p\) and \(q\) are \(k\)-bit prime numbers such that \(\mathrm{gcd}(pq, (p - 1) (q - 1)) = 1\), \(n = p q\), \(\lambda = (p - 1) (q - 1)\), \(\mu = \lambda^{-1} \bmod n\), and \(g = n + 1\). The plaintext and ciphertext spaces are \(\mathcal{M} = \mathbb{Z}_n\) and \(\mathcal{C} = \mathbb{Z}_n^\ast\), respectively.

Encryption

The encryption algorithm takes the public parameters, public key, and a plaintext \(m \in \mathcal{M}\) as input and outputs

\[ g^m r^n \bmod n^2, \]

where \(r \in \mathbb{Z}_n^\ast\) is a random number such that \(\mathrm{gcd}(r, n) = 1\).

Decryption

The decryption algorithm takes the public parameters, secret key, and a ciphertext \(c \in \mathcal{C}\) as input and outputs

\[ \frac{ (c^\lambda \bmod n^2) - 1 }{ n } \mu \bmod n. \]

Addition

The addition algorithm takes the public parameters and two ciphertexts \(c_1, c_2 \in \mathcal{C}\) as input and outputs

\[ c_1 c_2 \bmod n^2. \]

Integer multiplication

The integer multiplication algorithm takes the public parameters, a plaintext \(m \in \mathcal{M}\), and a ciphertext \(c \in \mathcal{C}\) as input and outputs

\[ c^m \bmod n^2. \]