Sieve, Enumerate, Slice, and Lift:

DOI10.1007/978-3-030-51938-4_15MaRDI QIDQ5048976zbMATH OpenOpenAlexFDO

Authors Emmanouil Doulgerakis, Thijs Laarhoven, Benne de Weger

Publication date 9 November 2022

Published in Progress in Cryptology - AFRICACRYPT 2020 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-51938-4_15

zbMATH Keywords

closest vector problem (CVP)lattice enumerationlattice sievingrandomized slicershortest vector problem (SVP)

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Algorithms in computer science (68Wxx) Cryptography (94A60)

Cites work

• A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
• A hierarchy of polynomial time lattice basis reduction algorithms
• A sieve algorithm for the shortest lattice vector problem
• Algorithms for the shortest and closest lattice vector problems
• BKZ
• BKZ 2.0: Better lattice security estimates
• Fast lattice point enumeration with minimal overhead
• Faster exponential time algorithms for the shortest vector problem
• Finding closest lattice vectors using approximate Voronoi cells
• Finding the closest lattice point by iterative slicing
• scientific article; zbMATH DE number 1962809 (Why is no real title available?)
• Improved algorithms for the approximate k-List problem in Euclidean norm
• Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
• Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
• Lattice enumeration using extreme pruning
• New directions in nearest neighbor searching with applications to lattice sieving
• On Lovász' lattice reduction and the nearest lattice point problem
• Progressive lattice sieving
• Random sampling revisited: lattice enumeration with discrete pruning
• Shortest vector from lattice sieving: a few dimensions for free
• Sieve algorithms for the shortest vector problem are practical
• Sieving for closest lattice vectors (with preprocessing)
• Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
• Solving the shortest vector problem in 2ⁿ time using discrete Gaussian sampling (extended abstract)
• Speed-ups and time-memory trade-offs for tuple lattice sieving
• The general sieve kernel and new records in lattice reduction
• Tuple lattice sieving

Cited in

(6)

• Lower bounds on lattice sieving and information set decoding
• Approx-SVP in ideal lattices with pre-processing
• Twisted-PHS: using the product formula to solve approx-SVP in ideal lattices
• On the SVP for low-dimensional circulant lattices
• Heuristic algorithm for solving restricted SVP and its applications
• Dual lattice attacks for closest vector problems (with preprocessing)

Describes a project that uses

Uses Software

• BKZ
• fpLLL
• GitHub

This page was built for publication: Sieve, Enumerate, Slice, and Lift:

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