Cryptology ePrint Archive: Report 2014/437
Rounding and Chaining LLL: Finding Faster Small Roots of Univariate Polynomial Congruences
Jingguo Bi and Jean-Sébastien Coron and Jean-Charles Faugère and Phong Q. Nguyen and Guénaël Renault and Rina Zeitoun
Abstract: 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é{\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.
Category / Keywords: public-key cryptography / Coppersmith's Algorithm, Small Roots of Polynomial Equations, LLL, Complexity, Speedup, RSA.
Date: received 6 Jun 2014, last revised 6 Jun 2014
Contact author: r zeitoun at oberthur com
Available format(s): PDF | BibTeX Citation
Version: 20140612:032853 (All versions of this report)
Short URL: ia.cr/2014/437
[ Cryptology ePrint archive ]