The Paillier cryptosystem was first presented in the 1999 paper “Public-Key Cryptosystems Based on Composite Degree Residuosity Classes” by Pascal Paillier. It is a public key encryption scheme that uses a novel cryptographic assumption, and furthermore has the property that the encryption is additively homomorphic–multiplying two ciphertexts results in a ciphertext that decrypts to the sum of the two messages.
Recall that an public key encryption scheme is given by three functions: key generation, encryption, decryption. I present the construction below and then show why it works, filling in some proof details that are glossed over by the original paper.
Key Generation
We pick two large primes \(p\) and \(q\) of about the same size (for example, say \(p\) and \(q\) have same number of bits). Let \(n=pq\).
We define \(B_{\alpha}=\{g \in (\mathbb{Z}/n^2\mathbb{Z})^{\times}\mid \text{ord}(g)=\alpha n\}\) (\(B_\alpha\) is the set of all elements in the multiplicative group of integers modulo \(n^2\) where the order is \(\alpha n\)).
Let \(B=\cup_{\alpha=1}^{\lambda(n)} B_{\alpha}\), where \(\lambda\) is the Carmichael function.
We pick some \(g\in B\). The public key is the pair of values \((n,g)\) and the secret key is the factorization of \(n\), which is the pair \((p,q)\).
Encryption
We can encode the message \(m\) as some number in the range \([0...n-1]\). We also pick a random value \(r\in [0...n-1]\). Using the public key \((n,g)\) encrypt \(m\) as the ciphertext \(c=g^mr^n \mod n^2\).
Decryption
Given a ciphertext \(c\), we recover the message \(m=\frac{L(c^{\lambda(n)} \mod n^2)}{L(g^{\lambda(n)} \mod n^2)}\), where \(L\) is the function \(L(u)=\frac{u-1}{n}\). We use the secret key in calculating the Carmichael function of \(n\), since \(\lambda(n)=\text{lcm}(p-1,q-1)\).
Proposition 1: For any \(w\in (\mathbb{Z}/n^2\mathbb{Z})^{\times}\) and \(g\in B\), there exists unique \(x \in \mathbb{Z}/n\mathbb{Z}\), \(y\in (\mathbb{Z}/n\mathbb{Z})^\times\) such that \(w=g^xy^n\mod n^2\).
Proof: We show that the map \(f: (x,y) \mapsto g^xy^n \mod n^2\) is a bijection.
We have that \(f: \mathbb{Z}/n\mathbb{Z} \times (\mathbb{Z}/n\mathbb{Z})^{\times} \to (\mathbb{Z}/n^2\mathbb{Z})^{\times}\).
\(\vert\mathbb{Z}/n\mathbb{Z}\vert=n\) and \(\vert(\mathbb{Z}/n\mathbb{Z})^{\times}\vert=\phi(n)\), so \(\vert \mathbb{Z}/n\mathbb{Z} \times (\mathbb{Z}/n\mathbb{Z})^{\times} \vert=n\phi(n)\), where \(\phi\) is Euler’s totient function.
\(\vert (\mathbb{Z}/n^2\mathbb{Z})^{\times} \vert=\phi(n^2)\), but we have that:
\[\begin{align*} \phi(n^2)&=n^2(1-\frac{1}{p})(1-\frac{1}{q})\\ &= n[n(1-\frac{1}{p})(1-\frac{1}{q})]\\ &= n\phi(n) \end{align*}\]So \(\vert \mathbb{Z}/n\mathbb{Z} \times (\mathbb{Z}/n\mathbb{Z})^{\times} \vert = \vert (\mathbb{Z}/n^2\mathbb{Z})^{\times} \vert\). Therefore, \(f\) is bijective if it is injective.
Consider \((x_1,y_1),(x_2,y_2) \in \mathbb{Z}/n\mathbb{Z} \times (\mathbb{Z}/n\mathbb{Z})^{\times}\) and suppose that \(f(x_1,y_1)=f(x_2,y_2)\). That means that \(g^{x_1}y_1^n\mod n^2=g^{x_2}y_2^n\mod n^2\). Dividing one expression by the other, we have that \(g^{x_2-x_1}(\frac{y_2}{y_1})^n = 1\mod n^2\).
Exponentiating both sides by \(\lambda(n)\), we have \(g^{(x_2-x_1)\lambda(n)}(\frac{y_2}{y_1})^{n\lambda(n)} = 1\mod n^2\).
Using the definition of the Carmichael function, we have that:
\[\begin{align*} \lambda(n^2)&=\text{lcm}(\lambda(p),\lambda(q))\\ &=\text{lcm}(\phi(p^2),\phi(q^2))\\ &=\text{lcm}(p(p-1), q(q-1))\\ &=pq\text{lcm}(p-1,q-1)\\ &=n\lambda(n) \end{align*}\]Since \(\lambda(n^2)\) is the exponent of the group \((\mathbb{Z}/n^2\mathbb{Z})^{\times}\), \((\frac{y_2}{y_1})^{n\lambda(n)} = 1\mod n^2\), giving us \(g^{(x_2-x_1)\lambda(n)} = 1\mod n^2\).
\(g\in B\), so its order in \((\mathbb{Z}/n^2\mathbb{Z})^{\times}\) is a non-zero multiple of \(n\). That means that \((x_2-x_1)\lambda(n)\) is a multiple of \(n\).
\(\text{gcd}(\lambda(n), n)=1\), since if it were not, \(\lambda(n)\) would be divisible by \(p\) or \(q\). WLOG, suppose it was divisible by \(p\). \(\lambda(n)=\text{lcm}(p-1, q-1)\), \(p\) clearly cannot divide \(p-1\), and given that \(p\) and \(q\) are large and are roughly the same size, \(p > \sqrt{q-1}\) so \(p\) also cannot divide \(q-1\). \(p\) cannot divide \(\lambda(n)\).
\(\text{gcd}(\lambda(n), n)=1\) means that \(x_2-x_1\) is a multiple of \(n\), but since \(x_1\) and \(x_2\) were from \(\mathbb{Z}/n\mathbb{Z}\), \(x_1=x_2\). It then follows that \(g^{x_2-x_1}(\frac{y_2}{y_1})^n = g^0(\frac{y_2}{y_1})^n = (\frac{y_2}{y_1})^n =1\mod n^2\). So, \(y_1=y_2\), proving injectivity.
\(f\) is a bijection, so for any \(w\in (\mathbb{Z}/n^2\mathbb{Z})^{\times}\) and \(g\in B\), there exists unique \(x \in\), \(y\in\) such that \(f(x,y)=w\). \(\square\)
We can define for \(w\in (\mathbb{Z}/n^2\mathbb{Z})^{\times}\) and \(g\in B\) the class of \(w\) with respect to \(g\), \([[w]]_g\). We define \([[w]]_g\) to be the unique \(x\) where \(w=g^{x}y^n\mod n^2\), which follows from Proposition 1. The Paillier encryption scheme is secure against chosen plaintext attacks under the assumption that computing \([[w]]_g\) is hard (specifically, the decisional version of this problem).
Proposition 2: \(L(w^{\lambda(n)}\mod n^2)=\lambda(n)[[w]]_{n+1} \mod n\)
Proof: We have that \(n+1\in B\) because by the binomial expansion:
\[\begin{align*} (n+1)^k&=\sum_{i=0}^{k}\binom{k}{i}n^i\\ &= kn+1 \mod n^2 \end{align*}\]The smallest positive integer \(k\) for which \(kn+1\mod n^2 = 1\) is when \(k=n\), so the order of \(n+1\) is \(n\), a non-zero multiple of \(n\).
So, \(\exists x,y\) such that \(w=(n+1)^xy^n \mod n^2\) by Proposition 1, and \([[w]]_{n+1}=x\) by definition.
Exponentiate both sides by \(\lambda(n)\). We get \(w^{\lambda(n)}=(n+1)^{x\lambda(n)}y^{n\lambda(n)}\mod n^2\).
So \(y^{n\lambda(n)}= 1 \mod n^2\), giving us \(w^{\lambda(n)}=(n+1)^{x\lambda(n)}\mod n^2=xn\lambda(n)+1\mod n^2\).
\(\lambda(n)x=\frac{w^{\lambda(n)}-1}{n}\mod n^2\) so the proposition holds. \(\square\)
Proposition 3: For \(w\in (\mathbb{Z}/n^2\mathbb{Z})^{\times}\) and \(g_1,g_2\in B\), \([[w]]_{g_2}=\frac{[[w]]_{g_1}}{[[g_2]]_{g_1}} \mod n\)
Proof: We first show \([[w]]_{g_2}=[[w]]_{g_1}[[g_1]]_{g_2} \mod n\). Suppose that \(w=g_1^{x_1}y_1^n\mod n^2\) and \(g_1=g_2^{x_2}y_2^n\mod n^2\) giving us \([[w]]_{g_1}=x_1\) and \([[g_1]]_{g_2}=x_2\).
We have that:
\[\begin{align*} g_2^{x_1x_2}(y_1y_2^{x_1})^n &= (g_2^{x^2}y_2^n)^{x_1}y_2^{-x_1n}(y_1y_2^{x_1})^n\\ &=g_1^{x_1}y_1^n\mod n^2\\ &=w \end{align*}\]So \([[w]]_{g_2}=x_1x_2=[[w]]_{g_1}[[g_1]]_{g_2}\mod n\).
If we plug in \(g_2\) for \(w\), we have that \([[g_2]]_{g_2}=x_1x_2=[[g_2]]_{g_1}[[g_1]]_{g_2}\mod n\).
But \([[g_2]]_{g_2}=1\), so \([[g_2]]_{g_1}^{-1}=[[g_1]]_{g_2}\mod n\).
We can therefore substitute \([[g_1]]_{g_2}\) and get \([[w]]_{g_2}=[[w]]_{g_1}[[g_1]]_{g_2} \mod n\). \(\square\)
Theorem: The decryption of the Paillier cryptosystem is correct.
Proof:
\[\begin{align*} \frac{L(c^{\lambda(n)}\mod n^2)}{L(g^{\lambda(n)}\mod n^2)} &= \frac{\lambda(n)[[c]]_{n+1}}{\lambda(n)[[g]]_{n+1}} &&\text{(Proposition 2)}\\ &=\frac{[[c]]_{n+1}}{[[g]]_{n+1}}\\ &=[[c]]_{g} && \text{(Proposition 3)}\\ &=m \text{ } \square \end{align*}\] Written on October 30th, 2020 by Alex Miao