Rounding and Chaining LLL: Finding Faster Small Roots of Univariate Polynomial Congruences
Speaker(s) : Rina ZEITOUN ( PolSys team, CNRS/INRIA/UPMC & Oberthur Technologies)
In this talk, I will present the first significant speedups over Coppersmith's algorithm for finding small roots of univariate polynomial congruences.
Coppersmith's method 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. The first speedup that we present 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 L^2 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.
This is a joint work with Jingguo Bi, Jean-Sébastien Coron, Jean-Charles Faugère, Phong Q. Nguyen and Guénaël Renault.
Elias.Tsigaridas (at) nulllip6.fr