# When e-th Roots Become Easier Than Factoring

3 CACAO - Curves, Algebra, Computer Arithmetic, and so On
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We show that computing e-th roots modulo n is easier than factoring n with currently known methods, given subexponential access to an oracle outputting the roots of numbers of the form $x_i + c$. Here $c$ is fixed and $x_i$ denotes small integers of the attacker’s choosing.The attack comes in two flavors:– A first version is illustrated here by producing selective roots of the form $x_i + c$ in $L_n(1/3, \sqrt[3]{32/9})$. This matches the special number field sieve’s (SNFS) complexity.– A second variant computes arbitrary $e$-th roots in $L_n(1/3, γ)$ after a subexponential number of oracle queries. The constant γ depends onthe type of oracle used.This addresses in particular the One More RSA Inversion problem, where the $e$-th root oracle is not restricted to numbers of a special form. The aforementioned constant γ is then $\sqrt[3]{32/9}$.If the oracle is constrained to roots of the form $\sqrt[e]{x_i + c \mod n}$, then $γ = \sqrt[3]{6}$.Both methods are faster than factoring n using the GNFS ($L_n(1/3, \sqrt[3]{64/9})$). This sheds additional light on RSA’s malleability in general and on RSA’sresistance to affine forgeries in particular – a problem known to be polynomial for $x_i > \sqrt[3]{n}$, but for which no algorithm faster than factoringwas known before this work.
Keywords :
Document type :
Conference papers

Cited literature [16 references]

https://hal.inria.fr/inria-00187782
Contributor : Emmanuel Thomé Connect in order to contact the contributor
Submitted on : Thursday, November 15, 2007 - 11:41:44 AM
Last modification on : Wednesday, October 20, 2021 - 12:24:14 AM
Long-term archiving on: : Monday, September 24, 2012 - 3:26:22 PM

### File

nfsforge.pdf
Files produced by the author(s)

### Citation

Antoine Joux, David Naccache, Emmanuel Thomé. When e-th Roots Become Easier Than Factoring. Advances in Cryptology -- ASIACRYPT 2007, Dec 2007, Kuching, Malaysia. pp.13-28, ⟨10.1007/978-3-540-76900-2_2⟩. ⟨inria-00187782⟩

Record views