Paper 2013/483

A Variant of Coppersmith's Algorithm with Improved Complexity and Efficient Exhaustive Search

Jean-Sébastien Coron, Jean-Charles Faugère, Guénaël Renault, and Rina Zeitoun

Abstract

Coppersmith described at Eurocrypt 96 a polynomial-time algorithm for finding small roots of univariate modular equations, based on lattice reduction. In this paper we describe the first improvement of the asymptotic complexity of Coppersmith's algorithm. Our method consists in taking advantage of Coppersmith's matrix structure, in order to apply LLL algorithm on a matrix whose elements are smaller than those of Coppersmith's original matrix. Using the $L^2$ algorithm, the asymptotic complexity of our method is $O(\log^{6+\epsilon} N)$ for any $\epsilon > 0$, instead of $O(\log^{8+\epsilon} N)$ previously. Furthermore, we devise a method that allows to speed up the exhaustive search which is usually performed to reach Coppersmith's theoretical bound. Our approach takes advantage of the LLL performed to test one guess, to reduce complexity of the LLL performed for the next guess. Experimental results confirm that it leads to a considerable performance improvement.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Coppersmith's MethodLLLStructured Matrix
Contact author(s)
r zeitoun @ oberthur com
History
2013-08-14: received
Short URL
https://ia.cr/2013/483
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/483,
      author = {Jean-Sébastien Coron and Jean-Charles Faugère and Guénaël Renault and Rina Zeitoun},
      title = {A Variant of Coppersmith's Algorithm with Improved Complexity and Efficient Exhaustive Search},
      howpublished = {Cryptology ePrint Archive, Paper 2013/483},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/483}},
      url = {https://eprint.iacr.org/2013/483}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.