IACR News item: 17 August 2013
Jingguo Bi, Phong Q. Nguyen
ePrint Reportthis 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\\\'e L^2 algorithm.
Additional news items may be found on the IACR news page.