Rounding and Chaining LLL: Finding Faster Small Roots of Univariate Polynomial Congruences

Jingguo Bi 1, 2 Jean-Sébastien Coron 3 Jean-Charles Faugère 4 Phong Q. Nguyen 1, 2 Guénaël Renault 4 Rina Zeitoun 4, 5
1 Institute for Advanced Study [Tsinghua]
2 CRYPT - Cryptanalyse
LIAMA - Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées, Inria Paris-Rocquencourt
3 Uni.lu - Université du Luxembourg
4 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
5 Oberthur Card Systems - Puteaux
Abstract : In a seminal work at EUROCRYPT '96, Coppersmith showed how to find all small roots of a univariate polynomial congruence in polynomial time: this has found many applications in public-key cryptanalysis and in a few security proofs. However, the running time of the algorithm is a high-degree polynomial, which limits experiments: the bottleneck is an LLL reduction of a high-dimensional matrix with extra-large coefficients. We present in this paper the first significant speedups over Coppersmith's algorithm. The first speedup is based on a special property of the matrices used by Coppersmith's algorithm, which allows us to provably speed up the LLL reduction by rounding, and which can also be used to improve the complexity analysis of Coppersmith's original algorithm. The exact speedup depends on the LLL algorithm used: for instance, the speedup is asymptotically quadratic in the bit-size of the small-root bound if one uses the Nguyen-Stehlé L2 algorithm. The second speedup is heuristic and applies whenever one wants to enlarge the root size of Coppersmith's algorithm by exhaustive search. Instead of performing several LLL reductions independently, we exploit hidden relationships between these matrices so that the LLL reductions can be somewhat chained to decrease the global running time. When both speedups are combined, the new algorithm is in practice hundreds of times faster for typical parameters.
Keywords : RSA LLL Small Roots of Polynomial Equations Coppersmith's Algorithm
Type de document :
Communication dans un congrès
Hugo Krawczyk. PKC 2014 - 17th IACR International Conference on Practice and Theory of Public-Key Cryptography, Mar 2014, Buenos Aires, Argentina. Springer, 8383, pp.185-202, 2014, Lecture Notes in Computer Science. 〈10.1007/978-3-642-54631-0_11〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-00926902
Contributeur : Guénaël Renault <>
Soumis le : vendredi 10 janvier 2014 - 14:28:31
Dernière modification le : vendredi 31 août 2018 - 09:25:54
Document(s) archivé(s) le : jeudi 10 avril 2014 - 23:30:08

Fichier

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

Identifiants

Collections

INRIA | LIAMA | UPMC | LIP6 | CIRAD | INRA

Citation

Jingguo Bi, Jean-Sébastien Coron, Jean-Charles Faugère, Phong Q. Nguyen, Guénaël Renault, et al.. Rounding and Chaining LLL: Finding Faster Small Roots of Univariate Polynomial Congruences. Hugo Krawczyk. PKC 2014 - 17th IACR International Conference on Practice and Theory of Public-Key Cryptography, Mar 2014, Buenos Aires, Argentina. Springer, 8383, pp.185-202, 2014, Lecture Notes in Computer Science. 〈10.1007/978-3-642-54631-0_11〉. 〈hal-00926902〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

752

Téléchargements de fichiers

354

Contact


archive-ouverte@inria.fr