QR ⇒ Additively homomorphic encryption

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 twice the QR advantage

Statement

The Goldwasser–Micali scheme, with $\mathsf{pk}=(N,y)$ for $N=pq$ and $y\in {\mathrm{J}}_N\setminus {\mathrm{QR}}_N$ and $\mathsf{Enc}(\mathsf{pk},\beta ;r)=y^{\beta }{r}^2\mathrm{mod}N$ for $\beta \in \{0,1\}$ and $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_N^{\ast }$, is IND-CPA-secure if QR is hard — GM84. It is additively homomorphic over ${\mathbb{Z}}_2$: the product of encryptions of ${\beta }_1$ and ${\beta }_2$ is distributed exactly as a fresh encryption of ${\beta }_1\oplus {\beta }_2$ — standard.

Sketch

$(y^{{\beta }_1}{r}_1^2)(y^{{\beta }_2}{r}_2^2)=y^{{\beta }_1\oplus {\beta }_2}(y^{{\beta }_1{\beta }_2}{r}_1{r}_2{)}^2$, and $y^{{\beta }_1{\beta }_2}{r}_1{r}_2$ is uniform in ${\mathbb{Z}}_N^{\ast }$ when $r_1$ is. CPA security is the reduction on QR ⇒ PKE, which sets $y$ to the QR challenge.