The nearest-colattice algorithm: time-approximation tradeoff for approx-CVP

DOI10.2140/OBS.2020.4.251MaRDI QIDQ5853801zbMATH OpenOpenAlexFDO

Authors Thomas Espitau, Paul Kirchner

Publication date 11 March 2021

Published in Open Book Series (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2140/obs.2020.4.251

zbMATH Keywords

closest vector problemlattice

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms (68W40) Cryptography (94A60)

Recommendations

• Sieving for closest lattice vectors (with preprocessing)
• Approximate CVP\(_p\) in time \(2^{0.802n}\)
• scientific article; zbMATH DE number 6607548
• Lattice sparsification and the approximate closest vector problem
• Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!

Cited in

(11)

• Sieving for closest lattice vectors (with preprocessing)
• On the security of OSIDH
• A key-recovery attack against Mitaka in the t-probing model
• Shorter hash-and-sign lattice-based signatures
• \textsc{Antrag}: annular NTRU trapdoor generation. Making \textsc{Mitaka} as secure as FALCON
• On Gaussian sampling, smoothing parameter and application to signatures
• Heuristic algorithm for solving restricted SVP and its applications
• Updatable encryption from group actions
• Phoenix: hash-and-sign with aborts from lattice gadgets
• Fast slicer for Batch-CVP: making lattice hybrid attacks practical
• Dual lattice attacks for closest vector problems (with preprocessing)

This page was built for publication: The nearest-colattice algorithm: time-approximation tradeoff for approx-CVP

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