On Bounded Distance Decoding for General Lattices

DOI10.1007/11830924_41MaRDI QIDQ3595403zbMATH OpenOpenAlexFDO

Authors Yi-Kai Liu, Vadim Lyubashevsky, Daniele Micciancio

Publication date 28 August 2007

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11830924_41

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decoding (94B35)

Recommendations

• Polynomial time bounded distance decoding near Minkowski's bound in discrete logarithm lattices
• On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem
• The inapproximability of lattice and coding problems with preprocessing
• Improved Inapproximability of Lattice and Coding Problems With Preprocessing
• scientific article; zbMATH DE number 6820265

Cited in

(20)

• Polynomial time bounded distance decoding near Minkowski's bound in discrete logarithm lattices
• A note on BDD problems with _2-gap
• Non-Random Coding Error Bounds for Lattices
• Algorithms for the shortest and closest lattice vector problems
• The geometry of lattice cryptography
• Generalized minimum-distance decoding of Euclidean-space codes and lattices
• On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem
• Hardness of approximating the closest vector problem with pre-processing
• scientific article; zbMATH DE number 1792628 (Why is no real title available?)
• scientific article; zbMATH DE number 6820265 (Why is no real title available?)
• A time-distance trade-off for GDD with preprocessing: instantiating the DLW heuristic
• Hardness of bounded distance decoding on lattices in lp norms
• Kissing numbers and transference theorems from generalized tail bounds
• Revisiting the Sparsification Technique in Kannan’s Embedding Attack on LWE
• Classical reduction of gap SVP to LWE: a concrete security analysis
• On algebraic homomorphic encryption and its applications to doubly-efficient PIR
• Sparse linear regression and lattice problems
• Improved classical and quantum algorithms for the shortest vector problem via bounded distance decoding
• Exploring trade-offs in batch bounded distance decoding
• Dual lattice attacks for closest vector problems (with preprocessing)

This page was built for publication: On Bounded Distance Decoding for General Lattices

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