Paper 2013/512

Rounding LLL: Finding Faster Small Roots of Univariate Polynomial Congruences

Jingguo Bi and Phong Q. Nguyen

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 a polynomial speedup over Coppersmith's algorithm. Our improvement is based on a special property of the matrices used by Coppersmith's algorithm, which allows us to speed up the LLL reduction by rounding. The exact speedup depends on the LLL algorithm used: for instance, the speedup is quadratic in the bit-size of the small-root bound if one uses the Nguyen-Stehlé L^2 algorithm.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Coppersmith's AlgorithmSmall Roots of Polynomial EquationsLLLComplexitySpeedupRSA.
Contact author(s)
pnguyen @ di ens fr
History
2013-08-17: received
Short URL
https://ia.cr/2013/512
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/512,
      author = {Jingguo Bi and Phong Q.  Nguyen},
      title = {Rounding LLL:  Finding Faster Small Roots of Univariate Polynomial Congruences},
      howpublished = {Cryptology ePrint Archive, Paper 2013/512},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/512}},
      url = {https://eprint.iacr.org/2013/512}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.