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

Léo Ducas; Wessel van Woerden

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

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}
}