DCR ⇒ Additively homomorphic encryption

Fully-black-box reduction · standard model · Pai99 · security loss: Tight: one call to the IND-CPA adversary; semantic security is equivalent to DCR.

Statement

Under DCR, the Paillier cryptosystem is an IND-CPA-secure PKE that is additively homomorphic: for an RSA modulus $n$ and $g\in {\mathbb{Z}}_{n^2}^{\ast }$ of order divisible by $n$ (e.g. $g=n+1$), $\mathsf{Enc}(\mathsf{pk},m;r)=g^m\cdot r^n\mathrm{mod}{n}^2$ with $m\in {\mathbb{Z}}_n$ and $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_n^{\ast }$, and $\mathsf{Enc}(\mathsf{pk},m_1;r_1)\cdot \mathsf{Enc}(\mathsf{pk},m_2;r_2)\mathrm{mod}{n}^2$ encrypts $m_1+m_2\mathrm{mod}n$ — Pai99. Semantic security of the scheme is equivalent to DCR — Pai99.

Sketch

An encryption of $m$ is $g^m$ times a random $n$-th residue, so a DCR challenge $z$ embeds as $c^{\ast }=g^{m_b}\cdot z\mathrm{mod}{n}^2$: if $z$ is an $n$-th residue, $c^{\ast }$ is a fresh encryption of $m_b$; if $z$ is uniform, $c^{\ast }$ is independent of $b$. The reduction runs the IND-CPA adversary once.

Notes

• Damgård–Jurik generalize the scheme to modulus $n^{d+1}$ and message space ${\mathbb{Z}}_{n^d}$ for any $d\ge 1$, still additively homomorphic and semantically secure under DCR (higher-degree composite residuosity ⇒ additively homomorphic encryption) — DJ01.
• The Paillier cryptosystem admits threshold decryption (DCR ⇒ TPKE) — FPS00.