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

*Jean-Sébastien Coron and Jean-Charles Faugère and 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.

**Category / Keywords: **public-key cryptography / Coppersmith's Method, LLL, Structured Matrix

**Date: **received 7 Aug 2013

**Contact author: **r zeitoun at oberthur com

**Available format(s): **PDF | BibTeX Citation

**Version: **20130814:144217 (All versions of this report)

**Short URL: **ia.cr/2013/483

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]