# 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. 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.
Keywords :
Type de document :
Communication dans un congrès
Kaoru Kurosawa. 13th International Conference on the Theory and Application of Cryptology and Information Security - ASIACRYPT 2007, Dec 2007, Kuching, Malaysia. Springer Berlin / Heidelberg, 4833, pp.13-28, 2007, Lecture Notes in Computer Science. 〈10.1007/978-3-540-76900-2_2〉
Liste complète des métadonnées

Littérature citée [16 références]

https://hal.inria.fr/inria-00187782
Contributeur : Emmanuel Thomé <>
Soumis le : jeudi 15 novembre 2007 - 11:41:44
Dernière modification le : mardi 24 avril 2018 - 17:20:10
Document(s) archivé(s) le : lundi 24 septembre 2012 - 15:26:22

### Fichier

nfsforge.pdf
Fichiers produits par l'(les) auteur(s)

### Citation

Antoine Joux, David Naccache, Emmanuel Thomé. When e-th Roots Become Easier Than Factoring. Kaoru Kurosawa. 13th International Conference on the Theory and Application of Cryptology and Information Security - ASIACRYPT 2007, Dec 2007, Kuching, Malaysia. Springer Berlin / Heidelberg, 4833, pp.13-28, 2007, Lecture Notes in Computer Science. 〈10.1007/978-3-540-76900-2_2〉. 〈inria-00187782〉

### Métriques

Consultations de la notice

## 328

Téléchargements de fichiers