Welcome to the resource topic for 2012/108
Title:
On the Optimality of Lattices for the Coppersmith Technique
Authors: Yoshinori Aono, Manindra Agrawal, Takakazu Satoh, 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 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.
ePrint: https://eprint.iacr.org/2012/108
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .