Welcome to the resource topic for 2013/483
Title:
A Variant of Coppersmith’s Algorithm with Improved Complexity and Efficient Exhaustive Search
Authors: Jean-Sébastien Coron, Jean-Charles Faugère, Guénaël Renault, 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.
ePrint: https://eprint.iacr.org/2013/483
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .