$d$-th Composite Residuosity ⇒ Additively homomorphic encryption

Fully-black-box reduction · standard model · DJ01 · security loss: tight up to a factor 2: one call to the IND-CPA adversary, whose advantage is at most twice the residuosity advantage

Statement

For $d\ge 1$, under the higher-degree composite residuosity assumption with parameter $d$ — hardness of distinguishing $n^d$-th residues modulo $n^{d+1}$ from uniform — the Damgård–Jurik cryptosystem is an IND-CPA-secure additively homomorphic encryption scheme for addition modulo $n^d$: for an RSA modulus $n$, $\mathsf{Enc}(\mathsf{pk},m;r)=(1+n{)}^m\cdot r^{n^d}\mathrm{mod}{n}^{d+1}$ encrypts $m\in {\mathbb{Z}}_{n^d}$, and the product of two ciphertexts encrypts $m_1+m_2\mathrm{mod}{n}^d$ — DJ01. The case $d=1$ is Paillier’s scheme (DCR ⇒ additively homomorphic encryption) — Pai99. For every $d$ the assumption is equivalent to DCR — DJ01.

Sketch

The reduction embeds a challenge $z$ as $c^{\ast }=(1+n{)}^{m_b}\cdot z\mathrm{mod}{n}^{d+1}$: an $n^d$-th residue $z$ makes $c^{\ast }$ a fresh encryption of $m_b$, and a uniform $z$ makes $c^{\ast }$ uniform, independent of $b$. Decryption raises the ciphertext to a secret exponent that is $0\mathrm{mod}\lambda$ and $1\mathrm{mod}{n}^d$, with $\lambda =\mathrm{lcm}(p-1,q-1)$; this kills the $r^{n^d}$ component and leaves $(1+n{)}^m$, from which $m$ is read off digit by digit modulo $n,n^2,\dots ,n^d$ using the binomial expansion.

Notes

• A ciphertext has $(d+1)\log n$ bits for a $d\log n$-bit plaintext, an expansion factor $(d+1)/d$ that tends to $1$ as $d$ grows — DJ01.