Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases
| dc.creator | Hanrot, Guillaume | |
| dc.creator | Stehlé, Damien | |
| dc.date | 2008-01-22 | |
| dc.date | 2008-01-24 | |
| dc.date.accessioned | 2026-07-07T08:56:00Z | |
| dc.date.available | 2026-07-07T08:56:00Z | |
| dc.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. | |
| dc.identifier | https://arxiv.org/abs/0801.3331 | |
| dc.identifier | http://arxiv.org/abs/0801.3331 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/146461 | |
| dc.subject | Number Theory | |
| dc.subject | Computational Complexity | |
| dc.subject | Cryptography and Security | |
| dc.title | Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases | |
| dc.type | text |