QR ⇒ COM

Standard model · folklore

Statement

QR implies a perfectly binding, computationally hiding bit commitment. With $\mathsf{pp}=(N,y)$ for $N=pq$ and $y\stackrel{\$}{\leftarrow }{\mathrm{J}}_N\setminus {\mathrm{QR}}_N$, a commitment to $b\in \{0,1\}$ is $c=y^b{r}^2\mathrm{mod}N$ for $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_N^{\ast }$, opened by revealing $(b,r)$. Binding is perfect since $c\in {\mathrm{QR}}_N$ iff $b=0$; hiding holds under QR since commitments to $0$ are uniform in ${\mathrm{QR}}_N$ and commitments to $1$ uniform in ${\mathrm{J}}_N\setminus {\mathrm{QR}}_N$ — folklore.

Sketch

The reduction embeds the QR challenge $a\in {\mathrm{J}}_N$ as $y$ and runs the hiding adversary once: if $a\notin {\mathrm{QR}}_N$ the hiding game is simulated exactly, and if $a\in {\mathrm{QR}}_N$ the commitment is a uniform square independent of $b$, so the adversary’s advantage decides residuosity (with a factor-$2$ loss).