Algorithm speeds up finding shortest vectors using less space
Faster SVP in Polynomial Space
Data Structures and Algorithms
Summary
Finding the shortest vector in a complex mathematical space is a tough problem important for fields like cryptography. Previous fastest methods that use reasonable computer memory took a long time to solve this. The authors improved the speed by cleverly representing that shortest vector in many ways and using a newer search method that reduces the work needed. This lets their algorithm solve the problem faster without using extra memory.
What this means in practice
- •For cryptography engineers: Improve security analysis of lattice-based cryptographic systems by enabling faster exact shortest vector solutions within practical memory limits.
- •For algorithm developers: Design more efficient algorithms for lattice computations using low-space randomization techniques derived from this improved shortest vector approach.
A theory result. No direct application yet.
Authors
Yansong Feng, Yiming Gao, Jiaqi Liu
Abstract
Kannan's algorithm, as analyzed by Hanrot and Stehlé 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.