SVP / Classical · ℓ∞ norm

Faster provable sieving algorithms for the Shortest Vector Problem and the Closest Vector Problem on lattices in ℓ_p norm

Priyanka Mukhopadhyay

Algorithms 2021

PublishedSource checked

Time bound: 2^{2.443 n + o(n)}
Space bound: 2^{2.443 n + o(n)}

Source / version date: 19 Dec 2021
Comparison variant: Classical · ℓ∞ norm
Cost scale: 2^{c n + o(n)}
Norm: ℓ∞
Success guarantee: At least 1/2
Computation model: Classical; polynomial input-size factors suppressed

Assumptions and source notes

Specializing the linear birthday sieve to ℓ∞, with the stated subdivision, yields the displayed bound at γ = 0.501 and ξ = 0.738. This improves the 2.82/2.82 specialization in Aggarwal–Mukhopadhyay 2018. The row is conservatively dated to the checked v3 rather than backdating the numerical refinement to v1.

Source location

§3.3, paragraph beginning “For p = ∞”; Table 1
Version: arXiv:1907.04406v3, 19 December 2021

Selected earlier references

Selected sources cited by this paper.

Improved algorithms for the Shortest Vector Problem and the Closest Vector Problem in the infinity norm
Divesh Aggarwal · Priyanka Mukhopadhyay · 2018
extends and refines the infinity-norm linear sieve v1 abstract; v3 §1.1.2, §3.3 and references [49,61]
Solving the Shortest Lattice Vector Problem in Time 2^(2.465n)
Xavier Pujol · Damien Stehlé · 2009
compares mixed Euclidean sieving with ListSieveBirthday v3 §4 comparison following Theorem 4.1; reference [28]
Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling
Divesh Aggarwal · Daniel Dadush · Oded Regev · Noah Stephens-Davidowitz · 2015
distinguishes the faster Euclidean DGS algorithm v3 §4 comparison and reference [20]
Algorithms for the Shortest and Closest Lattice Vector Problems
Guillaume Hanrot · Xavier Pujol · Damien Stehlé · 2011
uses the birthday-paradox analysis framework v3 §3.3 and references [26]

Primary source ↗

BibTeXDownload .bib

@article{mukhopadhyay-2019-lp-sieving,
  author = {Priyanka Mukhopadhyay},
  title = {{Faster provable sieving algorithms for the Shortest Vector Problem and the Closest Vector Problem on lattices in ℓ_p norm}},
  journal = {Algorithms},
  year = {2021},
  volume = {14},
  number = {12},
  pages = {362},
  doi = {10.3390/a14120362},
  url = {https://arxiv.org/abs/1907.04406},
  cr_date = {2019-07-09},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {Algorithms},
  cr_author_ids = {priyanka-mukhopadhyay},
  note = {arXiv:1907.04406; v1 9 July 2019, v3 19 December 2021}
}