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.