International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 12 June 2014

Jingguo Bi, Jean-S\\\'ebastien Coron, Jean-Charles Faug\\`ere, Phong Q. Nguyen, Gu\\\'ena\\\"
ePrint Report ePrint Report
In a seminal work at EUROCRYPT \'96, Coppersmith showed how to find

all small roots of a univariate polynomial congruence in polynomial

time: this has found many applications in public-key cryptanalysis

and in a few security proofs. However, the running time of the

algorithm is a high-degree polynomial, which limits experiments: the

bottleneck is an LLL reduction of a high-dimensional matrix with

extra-large coefficients. We present in this paper the first

significant speedups over Coppersmith\'s algorithm. The first

speedup is based on a special property of the matrices used by

Coppersmith\'s algorithm, which allows us to provably speed up the

LLL reduction by rounding, and which can also be used to improve

the complexity analysis of Coppersmith\'s original algorithm.

The exact speedup depends on the LLL algorithm used: for instance,

the speedup is asymptotically quadratic in the bit-size of the

small-root bound if one uses the Nguyen-Stehl\\\'e {\\Ltwo}

algorithm. The second speedup is heuristic and applies whenever

one wants to enlarge the root size of Coppersmith\'s algorithm by

exhaustive search. Instead of performing several LLL reductions

independently, we exploit hidden relationships between these

matrices so that the LLL reductions can be somewhat chained to

decrease the global running time. When both speedups are combined,

the new algorithm is in practice hundreds of times faster for

typical parameters.

Expand

Additional news items may be found on the IACR news page.