Faster SVP in Polynomial Space
In the authors' words
Kannan's algorithm, as analyzed by Hanrot and Stehl\'e in 2007, solves the exact Euclidean shortest vector problem in polynomial space and time. In the classical setting with polynomial space, we obtain the first improvement on this bound via a randomized algorithm that runs in time. The main idea is to represent a fixed shortest vector in many ways as a difference of samples, thereby enabling the low-space collision search of Lyu and Zhu (SODA 2023) to replace exhaustive enumeration in the original analysis.
Main resultThe abstract does not state a limitation.
Appeared: Monday, September 21. arXiv. Preprint, not yet peer-reviewed.