No straight-line reduction from FAC to low-exponent RSA

Conditional · assuming Factoring assumption · BV98

Statement

If factoring is hard, there is no efficient straight-line reduction that factors $n$ while making a logarithmic number of queries to an oracle breaking low-exponent RSA: any such reduction, which computes on $n$ and on the oracle’s answers only by ring operations modulo $n$, converts into an efficient factoring algorithm that makes no oracle queries — BV98. Reductions that use the bit representation of the oracle’s answers, or make more queries, are not covered.

Notes

• Against generic ring algorithms, which access ${\mathbb{Z}}_n$ only through ring operations and equality tests, breaking RSA is equivalent to factoring — AM09, DLO24. That result restricts the RSA algorithm rather than the reduction and does not get around this barrier.