IACR News item: 14 August 2013
Jean-Sébastien Coron, Jean-Charles Faugère, Guénaël Renault, Rina Zeitoun
ePrint Report
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.
Additional news items may be found on the IACR news page.