Paper 2026/2084 Original: eprint.iacr.org/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.
- History
- 2026-09-18: last updated
- 2026-09-18: published
- Short URL
- https://ia.cr/2026/2084
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}