Paper 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.