Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Lattice, LLL, Cryptanalysis

Date: received 14 Oct 2021, last revised 15 Oct 2021

Contact author: wvw at cwi nl, l ducas at cwi nl

Available format(s): PDF | BibTeX Citation

Version: 20211015:084045 (All versions of this report)

Short URL: ia.cr/2021/1391


[ Cryptology ePrint archive ]