Slide reduction, revisited–Filling the gaps in SVP approximation. Aggarwal, D., Li, J., Nguyen, P. Q., & Stephens-Davidowitz, N. 2019.
Slide reduction, revisited–Filling the gaps in SVP approximation [link]Paper  abstract   bibtex   
We show how to generalize Gama and Nguyen's slide reduction algorithm [STOC '08] for solving the approximate Shortest Vector Problem over lattices (SVP). As a result, we show the fastest provably correct algorithm for $δ$-approximate SVP for all approximation factors $n^{1/2+ɛ} ≤ δ ≤ n^{O(1)}$. This is the range of approximation factors most relevant for cryptography.
@unpublished{ALNSSlideReduction19,
	title = {Slide reduction, revisited--{F}illing the gaps in {SVP} approximation},
	url = {http://arxiv.org/abs/1908.03724},
	author = {Aggarwal, Divesh and Li, Jianwei and Nguyen, Phong Q. and {Stephens-Davidowitz}, Noah},
	year = {2019},
	abstract = {We show how to generalize Gama and Nguyen's slide reduction algorithm [STOC '08] for solving the approximate Shortest Vector Problem over lattices (SVP). As a result, we show the fastest provably correct algorithm for $\delta$-approximate SVP for all approximation factors $n^{1/2+\varepsilon} \leq \delta \leq n^{O(1)}$. This is the range of approximation factors most relevant for cryptography.},
}

Downloads: 0