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 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.
Category / Keywords: foundations / Lattice, Coppersmith technique, Univariate equation, Impossibility result, RSA
Date: received 27 Feb 2012, last revised 15 Apr 2012
Contact author: aono at nict go jp
Available formats: PDF | BibTeX Citation
Version: 20120416:020136 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]