Sieve, Enumerate, Slice, and Lift:

DOI10.1007/978-3-030-51938-4_15OpenAlexW3029035689MaRDI QIDQ5048976FDOQ5048976

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

lattice enumerationclosest vector problem (CVP)lattice sievingshortest vector problem (SVP)randomized slicer

Mathematics Subject Classification ID

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

Cites Work

• scientific article; zbMATH DE number 1962809 (Why is no real title available?)
• 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
• Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
• Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
• Improved algorithms for the approximate \(k\)-List problem in Euclidean norm
• 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 Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
• Sieving for closest lattice vectors (with preprocessing)
• Solving the shortest vector problem in \(2^n\) 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 (5)

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

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)