Cryptology ePrint Archive: Report 2012/108

On the Optimality of Lattices for the Coppersmith Technique

Yoshinori Aono and Manindra Agrawal and Takakazu Satoh and Osamu Watanabe

Abstract: We investigate the Coppersmith technique for finding solutions of a univariate modular equation within a range given by range parameter U. This technique converts a given equation to an algebraic equation via a lattice reduction algorithm, and the choice of the lattice is crucial for the performance of the technique. This paper provides a way to analyze a general type of limitation of this lattice construction. Our analysis bounds the possible range of $U$ from above that is asymptotically equal to the bound given by the original result of Coppersmith. It means that Coppersmith has already given the best lattice construction. To show our result, we establish a framework for the technique by following the reformulation of Howgrave-Graham, and derive a condition, which we call the lattice condition, for the technique to work. We then provide a way to analyze a bound of U for achieving the lattice condition. Technically, we show that (i) the original result of Coppersmith achieves an optimal bound for U when constructing a lattice in a standard way. We then show evidence supporting that (ii) a non-standard lattice construction is generally difficult. We also report on computer experiments demonstrating the tightness of our analysis.

Category / Keywords: foundations / Lattice, Coppersmith technique, Univariate equation, Impossibility result, RSA

Date: received 27 Feb 2012, last revised 15 Apr 2012

Contact author: aono at nict go jp

Available formats: PDF | BibTeX Citation

Version: 20120416:020136 (All versions of this report)

Discussion forum: Show discussion | Start new discussion