BDD / Classical · polynomial query and advice

On Bounded Distance Decoding for General Lattices

Yi-Kai Liu · Vadim Lyubashevsky · Daniele Micciancio

APPROX/RANDOM 2006

PublishedSource checked

Time bound: poly(input size)
Space bound: poly(input size) advice

Source / version date: Aug 2006
Comparison variant: Classical · polynomial query and advice
Cost scale: Polynomial online time; radius in entry
Decoding radius: c sqrt(log n/n) lambda_1(L), suitable absolute c > 0
Advice size: Polynomial-size advice string, including the periodic-Gaussian estimator
Preprocessing cost: Unbounded target-independent preprocessing
Success guarantee: Advice supports every target within the promised radius
Query model: Polynomial-time online exact decoding

Assumptions and source notes

The decoding radius improves the O(lambda_1/n) predecessor. The asymptotic radius hides a suitable constant; no universal constant-radius guarantee is asserted.

Source location

Abstract; §3, Theorems 1 and 2
Version: RANDOM 2006 author version; month established by author publication page

Selected earlier references

Selected sources cited by this paper.

Finding the closest lattice vector when it's unusually close
Philip Klein · 2000
Identifies the earlier O(lambda_1/n) preprocessed radius and invokes the basis-relative randomized decoder. Abstract; §1.1; §3 Theorem 1
Lattice Problems in NP ∩ coNP
Dorit Aharonov · Oded Regev · 2005
Uses the periodic-Gaussian estimator developed for distance estimation, extending it to close-vector search. Abstract; §2 Lemma 2; reference [2]
Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
Jeffrey C. Lagarias · Hendrik W. Lenstra, Jr. · Claus-Peter Schnorr · 1990
Uses a Korkin–Zolotarev basis bound to relate the shortest Gram–Schmidt vector to lambda_1. §2 Lemma 1; §3; reference [14]

Primary source ↗

BibTeXDownload .bib

@inproceedings{liu-lyubashevsky-micciancio-2006,
  author = {Yi-Kai Liu and Vadim Lyubashevsky and Daniele Micciancio},
  title = {{On Bounded Distance Decoding for General Lattices}},
  booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2006)},
  year = {2006},
  pages = {450--461},
  doi = {10.1007/11830924_41},
  url = {https://doi.org/10.1007/11830924_41},
  cr_date = {2006-08-31},
  cr_status = {published},
  cr_venue = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2006)},
  cr_author_ids = {yi-kai-liu; vadim-lyubashevsky; daniele-micciancio}
}