On the Optimality of Lattices for the Coppersmith Technique

Yoshinori Aono; Manindra Agrawal; Takakazu Satoh; Osamu Watanabe

Paper 2012/108

On the Optimality of Lattices for the Coppersmith Technique

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

Abstract

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 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 that satisfies these conditions. Technically, we show that the original result of Coppersmith achieves the optimal bound for when constructing a lattice in the standard way. We then provide evidence which indicates that constructing a non-standard lattice is generally difficult.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Unknown status
Keywords: Coppersmith technique Lattice construction Impossibility result RSA cryptanalyses
Contact author(s): aono @ nict go jp
History: 2015-12-18: last of 3 revisions; 2012-02-29: received; See all versions
Short URL: https://ia.cr/2012/108
License: CC BY

BibTeX

@misc{cryptoeprint:2012/108,
      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},
      url = {https://eprint.iacr.org/2012/108}
}