QR ⇒ PKE

Fully-black-box reduction · standard model · GM84 · security loss: tight up to a factor 2: one run of the CPA adversary with the QR challenge as the public key, whose advantage is at most twice the QR advantage

Statement

If QR is hard, the Goldwasser–Micali scheme is an IND-CPA-secure PKE for one-bit messages: $\mathsf{pk}=(N,y)$ with $N=pq$ and $y\in {\mathrm{J}}_N\setminus {\mathrm{QR}}_N$, $\mathsf{sk}=(p,q)$; $\mathsf{Enc}(\mathsf{pk},\beta )=y^{\beta }{r}^2\mathrm{mod}N$ for $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_N^{\ast }$; $\mathsf{Dec}$ outputs $0$ iff the ciphertext lies in ${\mathrm{QR}}_N$, decided with $(p,q)$. Encryptions of $0$ are uniform in ${\mathrm{QR}}_N$ and encryptions of $1$ uniform in ${\mathrm{J}}_N\setminus {\mathrm{QR}}_N$, so IND-CPA security is equivalent to QR — GM84.

Sketch

The reduction sets $y$ to the QR challenge $a$: if $a\notin {\mathrm{QR}}_N$ it simulates the real scheme exactly, and if $a\in {\mathrm{QR}}_N$ encryptions of $0$ and $1$ are identically distributed, so the IND-CPA advantage decides the residuosity of $a$. Conversely a QR decider decrypts.

Notes

• GM84 introduce semantic security, and this scheme is the first PKE proved to achieve it — GM84.
• Efficiency: each plaintext bit costs a squaring and a multiplication modulo $N$ and becomes an element of ${\mathbb{Z}}_N^{\ast }$, so ciphertexts are $\log N$ times longer than plaintexts; decryption computes one Legendre symbol modulo $p$ per bit — standard.