Estimating the hidden overheads in the BDGL lattice sieving algorithm

DOI10.1007/978-3-031-17234-2_22MaRDI QIDQ6166998zbMATH OpenOpenAlexFDO

Authors Léo Ducas

Publication date 7 July 2023

Published in Post-Quantum Cryptography (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-17234-2_22

zbMATH Keywords

concrete cryptanalysislattice sieving

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Quantum cryptography (quantum-theoretic aspects) (81P94) Cryptography (94A60)

Recommendations

• Estimating quantum speedups for lattice sieves
• Lower bounds on lattice sieving and information set decoding
• BKZ 2.0: Better lattice security estimates
• Lattice Sieving via Quantum Random Walks
• Tuning GaussSieve for speed

Cites work

• A sieve algorithm for the shortest lattice vector problem
• Advanced lattice sieving on GPUs, with tensor cores
• BKZ 2.0: Better lattice security estimates
• Estimating quantum speedups for lattice sieves
• Faster Dual Lattice Attacks for Solving LWE with Applications to CRYSTALS
• Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing
• LWE with side information: attacks and concrete security estimation
• New directions in nearest neighbor searching with applications to lattice sieving
• Shortest vector from lattice sieving: a few dimensions for free
• Sieve algorithms for the shortest vector problem are practical
• Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
• The general sieve kernel and new records in lattice reduction
• Tuning GaussSieve for speed

Cited in

(3)

• A refined hardness estimation of LWE in two-step mode
• Assessing the impact of a variant of MATZOV's dual attack on Kyber
• Memory adds no cost to lattice sieving for computers in 3 or more spatial dimensions

This page was built for publication: Estimating the hidden overheads in the BDGL lattice sieving algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166998)