Paper 2026/2256

Affine-Padding Rabin-Oracle Factoring in $L_n\!\left(\frac{1}{3},\sqrt[3]{\frac{32}{9}}\right)$

Abstract

The 2007 algorithm of Joux, Naccache, and Thomé (\textsc{jnt}) shows that, with subexponential access to an $e$-th root oracle, one can forge \textsc{rsa} signatures for \emph{odd} $e$ in time close to the special number field sieve, without factoring the modulus; a recent \textsc{jnt} implementation by Shea et al.~\cite{Forge26} carried that attack to $1024$-bit \textsc{rsa}. We revisit the \textsc{jnt} construction at $e=2$, the Rabin case, where an $e$-th root oracle is a square-root oracle. A \emph{raw} square-root oracle factors $n=pq$ in one query, so it is of no interest; the interesting object is a \emph{redundancy-constrained} (affine-padded) Rabin oracle that returns a single canonical root and thereby resists the one-query attack. We show that a one-sided number field sieve against such an oracle produces a congruence of squares $X^2\equiv Y^2\pmod n$ with $X\not\equiv\pm Y$ with probability $\tfrac12$ per dependency, and hence \emph{factors} $n$ in special-number-field-sieve time \[ L_n \left(\frac{1}{3},{\sqrt[3]{\frac{32}{9}}}\right)\simeq L_n(1/3,{1.526\ldots}), \] strictly below the general number field sieve's \[ L_n \left(\frac{1}{3},{\sqrt[3]{\frac{64}{9}}}\right)\simeq L_n(1/3,{1.923\ldots}). \] The mechanism is a pleasant inversion: the sign ambiguity that the odd-$e$ algorithm must suppress becomes, at $e=2$, the very quantity that \textsl{leaks the factorization}. We give the algorithm in full --- \textsc{lll} polynomial selection for a quadratic field, a line sieve producing prime-ideal relations, quadratic characters, $\mathbb F_2$ linear algebra, and an exact number-field square root --- prove the half-rate splitting, and analyse the complexity, including the precise reason the attack collapses when the padding is a hash rather than an affine function of an attacker-chosen message. An open-source implementation realises every step. A small toy example run of it, from the padded modulus to the recovered factors, is given in Appendix~\ref{app:example}. Our implementation confirms a clear performance improvement in factoring speed.