Paper 2012/108

On the Optimality of Lattices for the Coppersmith Technique

Yoshinori Aono, Manindra Agrawal, Takakazu Satoh, and Osamu Watanabe


We investigate a method for finding small integer solutions of a univariate modular equation, that was introduced by Coppersmith and extended by May. We will refer this method as the Coppersmith technique. This paper provides a way to analyze a general limitations of the lattice construction for the Coppersmith technique. Our analysis upper bounds the possible range of $U$ that is asymptotically equal to the bound given by the original result of Coppersmith and May. This means that they have already given the best lattice construction. In addition, we investigate the optimality for the bivariate equation to solve the small inverse problem, which was inspired by Kunihiro's argument. In particular, we show the optimality for the Boneh-Durfee's equation used for RSA cryptoanalysis, To show our results, we establish framework for the technique by following the relation of Howgrave-Graham, and then concretely define the conditions in which the technique succeed and fails. We then provide a way to analyze the range of $U$ that satisfies these conditions. Technically, we show that the original result of Coppersmith achieves the optimal bound for $U$ when constructing a lattice in the standard way. We then provide evidence which indicates that constructing a non-standard lattice is generally difficult.

Available format(s)
Publication info
Published elsewhere. Unknown status
Coppersmith techniqueLattice constructionImpossibility resultRSA cryptanalyses
Contact author(s)
aono @ nict go jp
2015-12-18: last of 3 revisions
2012-02-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yoshinori Aono and Manindra Agrawal and Takakazu Satoh and Osamu Watanabe},
      title = {On the Optimality of Lattices for the Coppersmith Technique},
      howpublished = {Cryptology ePrint Archive, Paper 2012/108},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.