Factoring ⇒ TDP (Rabin)

Fully-black-box reduction · standard model · Rab79 · security loss: a factor 2: an inverter succeeding with probability ε factors N with probability ε/2

Statement

Let $N=pq$ be a Blum integer ($p\equiv q\equiv 3(\mathrm{mod}4)$). Squaring $x\mapsto x^2\mathrm{mod}N$ permutes the quadratic residues ${\mathrm{QR}}_N$, and $(p,q)$ is a trapdoor for it — BBS86. If factoring Blum integers is hard, this family is a trapdoor permutation: by Rabin’s argument that extracting square roots modulo $N$ is as hard as factoring, inverting it on a uniform element of ${\mathrm{QR}}_N$ with probability $\epsilon$ factors $N$ with probability $\epsilon /2$ — Rab79.

Sketch

Since $-1$ is a non-residue modulo $p$ and $q$, exactly one of the four square roots of each $y\in {\mathrm{QR}}_N$ is itself a residue, so squaring permutes ${\mathrm{QR}}_N$; with the trapdoor, $y^{(p+1)/4}\mathrm{mod}p$ and $y^{(q+1)/4}\mathrm{mod}q$ combine by the Chinese remainder theorem into that root. To factor, sample $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_N^{\ast }$, give the inverter $y=r^2\mathrm{mod}N$, which is uniform in ${\mathrm{QR}}_N$, and receive the residue root $x$; $r$ is uniform among the four roots of $y$ and independent of $x$, so $r\notin \{x,-x\}$ with probability $1/2$, and then $\gcd (r-x,N)$ is a prime factor.

Notes

• Efficiency: evaluation is one modular squaring, the cheapest of the standard trapdoor permutations; inversion costs two exponentiations modulo $p$ and $q$ and a Chinese remaindering — standard.
• Unlike RSA, whose inversion is not known to be as hard as factoring, inverting the Rabin function is equivalent to factoring; for low public exponents, an algebraic reduction from factoring to RSA inversion would yield an efficient factoring algorithm — BV98.
• Rab79 also derives signatures and public-key encryption from the same function — Rab79.