Higher residuosity ⇒ PKE

Fully-black-box reduction · standard model · CF85 · security loss: tight up to a factor 2: one run of the IND-CPA adversary with the challenge as the public non-residue $g$, whose advantage is at most twice the advantage of distinguishing a uniform $d$-th residue from a uniform $d$-th non-residue

Statement

The higher residuosity assumption implies IND-CPA-secure PKE with message space ${\mathbb{Z}}_d$, generalizing GM84 from quadratic to $d$-th power residues: for $N=pq$ with $d$ prime, $d\mid p-1$, $\gcd (d,(p-1)/d)=1$ and $d\nmid q-1$, and a fixed $d$-th non-residue $g\in {\mathbb{Z}}_N^{\ast }$, encrypt $m\in {\mathbb{Z}}_d$ as $g^m{u}^d\mathrm{mod}N$ for $u\stackrel{\$}{\leftarrow }{\mathbb{Z}}_N^{\ast }$ — CF85.

Sketch

The reduction sets $g$ to the higher-residuosity challenge, as the GM84 reduction does with the QR challenge: for a $d$-th non-residue the public key is distributed as in the scheme, and for a $d$-th residue every ciphertext is a uniform $d$-th residue, independent of the message. Knowing $\varphi (N)$, the decryptor computes $c^{\varphi (N)/d}=(g^{\varphi (N)/d}{)}^m$ and recovers $m$ by exhaustive search in the order-$d$ subgroup, efficient for $d\le \mathrm{poly}(\lambda )$.

Notes

• Dense variant with ciphertext expansion arbitrarily close to $1$ (the Benaloh cryptosystem) — Ben94.
• Corrected key-generation conditions for the dense scheme, whose original parameters can make decryption ambiguous — FLA11.
• Deterministic and probabilistic variants with smooth exponent and higher bandwidth — NS98.