IACR News item: 12 June 2014
Jingguo Bi, Jean-S\\\'ebastien Coron, Jean-Charles Faug\\`ere, Phong Q. Nguyen, Gu\\\'ena\\\"
ePrint Reportall 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.
Additional news items may be found on the IACR news page.