Algorithms for the Shortest and Closest Lattice Vector Problems
From MaRDI portal
Publication:3005588
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
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
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
