Title: Coppersmith's lattices and "focus groups": an attack on small-exponent RSA,
Abstract: We present a principled technique for reducing the matrix size in some
applications of Coppersmith's lattice method for finding roots of modular
polynomial equations. It relies on an analysis of the actual performance of
Coppersmith's attack for smaller parameter sizes, which can be thought of as
"focus group" testing. When applied to the small-exponent RSA problem, it
reduces lattice dimensions and consequently running times (sometimes by factors
of two or more). We also argue that existing metrics (such as enabling
condition bounds) are not as important as often thought for measuring the true
performance of attacks based on Coppersmith's method. Finally, experiments are
given to indicate that certain lattice reductive algorithms (such as
Nguyen-Stehlé's L2) may be particularly well-suited for Coppersmith's method.