Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

The Hermite-Korkine-Zolotarev reduction plays a central role in strong lattice reduction algorithms. By building upon a technique introduced by Ajtai, we show the existence of Hermite-Korkine-Zolotarev reduced bases that are arguably least reduced. We prove that for such bases, Kannan's algorithm solving the shortest lattice vector problem requires $d^{\frac{d}{2\e}(1+o(1))}$ bit operations in dimension $d$. This matches the best complexity upper bound known for this algorithm. These bases also provide lower bounds on Schnorr's constants $α_d$ and $β_d$ that are essentially equal to the best upper bounds. Finally, we also show the existence of particularly bad bases for Schnorr's hierarchy of reductions.

Keywords

Number Theory, Computational Complexity, Cryptography and Security

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/146461

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0801.3331
 http://arxiv.org/abs/0801.3331

Collections

arXiv