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

Category / Keywords: Coppersmith technique, Lattice construction, Impossibility result, RSA cryptanalyses

Date: received 27 Feb 2012, last revised 18 Dec 2015

Contact author: aono at nict go jp

Available format(s): PDF | BibTeX Citation

Version: 20151218:083231 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]