A note on a Claim of Eldar & Hallgren: LLL already solves it

Léo Ducas; Wessel van Woerden

Paper 2021/1391

A note on a Claim of Eldar & Hallgren: LLL already solves it

Léo Ducas and Wessel van Woerden

Abstract

In a recent talk of Hallgren on a joint work with Eldar (Sept 21, 2021, Simons Institute), a polynomial-time quantum algorithm for solving BDD in a certain class of lattices was claimed. We show here that known classical (and even, deterministic) polynomial-time algorithms already achieve this result.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: Lattice LLL Cryptanalysis
Contact author(s): wvw @ cwi nl
l ducas @ cwi nl
History: 2021-10-15: revised; 2021-10-15: received; See all versions
Short URL: https://ia.cr/2021/1391
License: CC BY

BibTeX

@misc{cryptoeprint:2021/1391,
      author = {Léo Ducas and Wessel van Woerden},
      title = {A note on a Claim of Eldar & Hallgren: LLL already solves it},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1391},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1391}},
      url = {https://eprint.iacr.org/2021/1391}
}