Paper 2026/2084
Faster SVP in Polynomial Space
Abstract
Kannan's algorithm, as analyzed by Hanrot and Stehl\'e in 2007, solves the exact Euclidean shortest vector problem in polynomial space and \(n^{\frac{n}{2e}+o(n)}\) time. In the classical setting with polynomial space, we obtain the first improvement on this bound via a randomized algorithm that runs in \(n^{\frac{n}{4e}+o(n)}\) 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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- LatticeShortest vector problemEnumeration
- Contact author(s)
-
fengyansong @ amss ac cn
qw1234567 @ mail ustc edu cn
ljqi @ amss ac cn - History
- 2026-09-22: approved
- 2026-09-18: received
- See all versions
- Short URL
- https://ia.cr/2026/2084
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2084,
author = {Yansong Feng and Yiming Gao and Jiaqi Liu},
title = {Faster {SVP} in Polynomial Space},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2084},
year = {2026},
url = {https://eprint.iacr.org/2026/2084}
}
