The randomized slicer for CVPP: sharper, faster, smaller, batchier

DOI10.1007/978-3-030-45388-6_1MaRDI QIDQ2055682zbMATH OpenOpenAlexFDO

Authors Léo Ducas, Thijs Laarhoven, Wessel P. J. van Woerden

Publication date 1 December 2021

Full work available at URL https://ir.cwi.nl/pub/30000

zbMATH Keywords

approximate Voronoi cellsclosest vector problem with preprocessinggraph-based nearest neighboursiterative slicerlattices

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Recommendations

• Approximate Voronoi cells for lattices, revisited
• Finding closest lattice vectors using approximate Voronoi cells
• Short paths on the Voronoi graph and closest vector problem with preprocessing
• Sieving for closest lattice vectors (with preprocessing)
• A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations

Cites work

• A decade of lattice cryptography
• A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
• A method for obtaining digital signatures and public-key cryptosystems
• A note on two problems in connexion with graphs
• A sieve algorithm for the shortest lattice vector problem
• Approximate Voronoi cells for lattices, revisited
• Finding closest lattice vectors using approximate Voronoi cells
• Finding the closest lattice point by iterative slicing
• Graph-based time-space trade-offs for approximate near neighbors
• Improved algorithms for the approximate k-List problem in Euclidean norm
• Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
• Introduction to post-quantum cryptography
• Lattice enumeration using extreme pruning
• New directions in cryptography
• New directions in nearest neighbor searching with applications to lattice sieving
• Quantum lattice enumeration and tweaking discrete pruning
• Random sampling revisited: lattice enumeration with discrete pruning
• Short paths on the Voronoi graph and closest vector problem with preprocessing
• Sieve algorithms for the shortest vector problem are practical
• Sieving for closest lattice vectors (with preprocessing)
• The general sieve kernel and new records in lattice reduction

Cited in

(8)

• Lower bounds on lattice sieving and information set decoding
• Sliced AETG: a memory-efficient variant of the AETG covering array generation algorithm
• The irreducible vectors of a lattice: some theory and applications
• On the security of OSIDH
• Heuristic algorithm for solving restricted SVP and its applications
• Fast slicer for Batch-CVP: making lattice hybrid attacks practical
• Cross-paradigm models of restricted syndrome decoding with application to CROSS
• Dual lattice attacks for closest vector problems (with preprocessing)

This page was built for publication: The randomized slicer for CVPP: sharper, faster, smaller, batchier

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