Algorithms for the Shortest and Closest Lattice Vector Problems

DOI10.1007/978-3-642-20901-7_10zbMath1272.68477OpenAlexW1742003405MaRDI QIDQ3005588

Xavier Pujol, Guillaume Hanrot, Damien Stehlé

Publication date: 8 June 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20901-7_10

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Number-theoretic algorithms; complexity (11Y16)

Related Items

Sieve, Enumerate, Slice, and Lift: ⋮ Balanced Integer Solutions of Linear Equations ⋮ Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing ⋮ Finding shortest lattice vectors faster using quantum search ⋮ Estimation of the hardness of the learning with errors problem with a restricted number of samples ⋮ Correcting noisy exponentiation black-boxes modulo a prime ⋮ Flat Tori with Large Laplacian Eigenvalues in Dimensions up to Eight ⋮ Efficient computation of multidimensional theta functions ⋮ On the complexity of quasiconvex integer minimization problem ⋮ Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems ⋮ A Note on Lattice Packings via Lattice Refinements ⋮ FPT-algorithms for some problems related to integer programming ⋮ List decoding of number field codes ⋮ Lattice preconditioning for the real relaxation branch-and-bound approach for integer least squares problems ⋮ On the complexity of the BKW algorithm on LWE ⋮ Unnamed Item ⋮ Dynamic trading under integer constraints ⋮ On compact representations of Voronoi cells of lattices ⋮ Clustering analysis of a dissimilarity: a review of algebraic and geometric representation ⋮ On the density of cyclotomic lattices constructed from codes

Uses Software

• Magma
• NTL
• NTRU
• fpLLL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of the covering radius problem
• Sampling methods for shortest vectors, closest vectors and successive minima
• On Lovász' lattice reduction and the nearest lattice point problem
• Algorithms to construct Minkowski reduced and Hermite reduced lattice bases
• A hierarchy of polynomial time lattice basis reduction algorithms
• Factoring polynomials with rational coefficients
• A note on optimal unimodular lattices
• New bounds in some transference theorems in the geometry of numbers
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• The Magma algebra system. I: The user language
• Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
• On the Dirichlet-Voronoi cell of unimodular lattices
• A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations
• On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem
• Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
• Sieve algorithms for the shortest vector problem are practical
• Parallel Shortest Lattice Vector Enumeration on Graphics Cards
• Lattice Enumeration Using Extreme Pruning
• Finding the Closest Lattice Point by Iterative Slicing
• The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice
• Accelerating Lattice Reduction with FPGAs
• On Bounded Distance Decoding for General Lattices
• Rigorous and Efficient Short Lattice Vectors Enumeration
• Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
• Lattice-based Cryptography
• Minkowski's Convex Body Theorem and Integer Programming
• Maximum likelihood sequence estimation from the lattice viewpoint
• Closest point search in lattices
• On the equidistribution of Hecke points
• On the Extremality of an 80-Dimensional Lattice
• A sieve algorithm for the shortest lattice vector problem
• Hermite’s Constant and Lattice Algorithms
• Progress on LLL and Lattice Reduction
• Inapproximability Results for Computational Problems on Lattices
• Covering cubes and the closest vector problem
• Predicting Lattice Reduction
• Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
• Rankin’s Constant and Blockwise Lattice Reduction
• Algorithmic Number Theory
• On lattices, learning with errors, random linear codes, and cryptography