QR ⇒ FAC

Fully-black-box reduction · standard model · folklore · security loss: tight: one factoring call; the QR advantage equals the factoring success probability

Statement

If QR is hard for moduli $N=pq$ with $p\equiv q\equiv 3(\mathrm{mod}4)$, then factoring such $N$ (Blum integers) is hard — folklore.

Sketch

Given a QR challenge $(N,a)$, run the factoring algorithm on $N$; if it returns a prime factor $p^{\prime }$, output $0$ iff $a^{(p^{\prime }-1)/2}\equiv 1(\mathrm{mod}{p}^{\prime })$, and otherwise output a uniform bit. For $a\in {\mathrm{J}}_N$, $\left(\frac{a}{p}\right)=\left(\frac{a}{q}\right)$, so $a\in {\mathrm{QR}}_N$ iff $a$ is a square modulo $p^{\prime }$, which Euler’s criterion decides; the QR advantage therefore equals the factoring success probability.

Notes

• The reduction preserves the modulus distribution: QR hardness for any distribution of $N=pq$ with $p,q$ distinct odd primes gives factoring hardness for the same distribution — folklore.
• Whether factoring hardness implies QR hardness is open — folklore.