FAC ⇒ Factoring Blum integers

Fully-black-box reduction · standard model · folklore · security loss: a factor of about 4: a factoring instance is a Blum integer with probability 1/4 - o(1)

Statement

If factoring $N=pq$ is hard for independent uniform $\lambda$-bit primes $p,q$, then factoring Blum integers ($p\equiv q\equiv 3(\mathrm{mod}4)$) is hard: for every efficient $\mathcal{A}$ that factors Blum integers with probability $\epsilon$, running $\mathcal{A}$ on a factoring instance factors it with probability at least $(1/4-o(1))\epsilon$ — folklore.

Sketch

The Blum distribution is the factoring distribution conditioned on $p\equiv q\equiv 3(\mathrm{mod}4)$. The $\lambda$-bit primes are equidistributed between the residue classes $1$ and $3$ modulo $4$ by the prime number theorem for arithmetic progressions, so the event has probability $1/4-o(1)$, and on it $\mathcal{A}$ sees a correctly distributed instance; success is checked by division — standard.

Notes

• The converse does not follow in the average case: a factoring algorithm may succeed on a non-negligible fraction of all moduli and fail on every Blum integer — folklore.