IACR paper details
Title  When eth Roots Become Easier Than Factoring 

Booktitle  IACR Eprint archive 

Pages  

Year  2007 

URL  http://eprint.iacr.org/2007/424 

Author  Antoine Joux 

Author  David Naccache 

Author  Emmanuel Thomé 

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.
Several variants of the attack are presented, with varying
assumptions on the oracle, and goals ranging from selective to
universal forgeries. The computational complexity of the attack
is $L_n(\frac{1}{3}, \sqrt[3]{\frac{32}{9}})$ in most significant
situations, which matches the {\sl
special} number field sieve's ({\sc snfs}) complexity.
This sheds additional light on {\sc rsa}'s malleability in
general and on {\sc rsa}'s resistance to affine forgeries in
particular  a problem known to be polynomial for $x_i >
\sqrt[3]{n}$, but for which no algorithm faster than factoring
was known before this work.


Search for the paper
@misc{eprint200713704,
title={When eth Roots Become Easier Than Factoring},
booktitle={IACR Eprint archive},
keywords={publickey cryptography /},
url={http://eprint.iacr.org/2007/424},
note={RSA, NFS, factoring, digital signatures Emmanuel.Thome@normalesup.org 13829 received 12 Nov 2007},
author={Antoine Joux and David Naccache and Emmanuel Thomé},
year=2007
}
Download a complete BibTeX file.