Paillier encryption

How it works

Paillier encryption works modulo $n^2$ for an RSA modulus $n = pq$. With the common choice $g = n + 1$, a message $m \in \mathbb{Z}_n$ with randomness $r$ coprime to $n$ is encrypted as $c = g^m r^n \bmod n^2$. Because $(1 + n)^m \equiv 1 + mn \pmod{n^2}$, the first factor is easy to compute and to read back.

To decrypt, raise $c$ to $\lambda = \operatorname{lcm}(p - 1, q - 1)$: the random factor disappears, $c^\lambda \equiv 1 + m\lambda n \pmod{n^2}$, and the function $L(u) = (u - 1)/n$ followed by multiplication with $\mu = \lambda^{-1} \bmod n$ leaves $m$.

The point of the scheme is its additive homomorphism: $E(m_1) \cdot E(m_2) \bmod n^2$ is an encryption of $m_1 + m_2 \bmod n$, and $E(m)^k$ one of $km$, computed without the private key. This is used in electronic voting, private aggregation and many secure computation protocols. Security (IND-CPA) rests on the decisional composite residuosity assumption; the scheme is malleable by design.