Skip to content

Solving the Shortest Vector Problem in 20.6039n Time via Mid-point Hessian

Aug 2026 · IACR Cryptology ePrint Archive · Vol 2026, pp. 1597 · 2 citations · ⚡ 1 influential · 40 references
Computer Science

TL;DR

The authors' algorithm searches for the class of a shortest vector by estimating the corresponding Hessians using discrete Gaussian samples, and optimize the algorithm using random sublattice cosets and various sampling technique, achieving the final complexity.

Abstract

We present randomized algorithms for the shortest vector problem (SVP). For the $n$-dimensional lattice $\mathcal L$, our algorithms solve SVP in time $2^{0.6039n+o(n)}$ classically and $2^{0.5411n+o(n)}$ quantumly and space $2^{0.5n+o(n)}$, improving the previous best algorithm running in $2^{n+o(n)}$ time and space of Aggarwal, Dadush, Regev, and Stephens-Davidowitz [STOC'15]. Our algorithms heavily use the property of the Hessian of the periodic Gaussian function at the half shortest vector: For a shortest vector $v \in \mathcal L$, the Hessian at $v/2$ has the eigenvector close to $v$, which can be used to recover $v$ using the (preprocessing) bounded distance decoding algorithm. Given the periodicity modulo $\mathcal L$, the candidate midpoints are indexed by the parity classes in $\mathcal L/2\mathcal L$. Our algorithm searches for the class of a shortest vector by estimating the corresponding Hessians using discrete Gaussian samples. We optimize the algorithm using random sublattice cosets and various sampling technique, achieving the final complexity. The optimization techniques may be of independent interest.

View source

Similar papers

Preprint Sep 2026

Improved Algorithms for the Remote Point Problem

Over finite fields, the problem admits a deterministic polynomial-time algorithm that achieves optimal remoteness $n-k$ and an algorithm that achieves remoteness $\Omega\left(\frac{n}{\max\{k, \log n\}} \log n\right)$.

Ben Lee Volk · 0 citations
Preprint Aug 2026

Faster FPRAS for the Permanent via Restricted Poincar\'e Inequalities and Coupled Flows

The permanent of an $n\times n$ $0/1$ matrix $A$ equals the number of perfect matchings in the bipartite graph with edges defined by $A$. Jerrum, Sinclair, and Vigoda (2004) presented an FPRAS for approximating the permanent of any nonnegative matrix using a novel simulated-annealing algorithm. The running time was imp...

Xiao-Yu Chen, Eric Vigoda, Xiong-Xin Yang · 2 citations
Preprint Sep 2026

Fast Algorithms for Sparse PCA and Robust Sparse Estimation

These certificate routines yield the first quadratic and subquadratic-time algorithms for robust sparse estimation for broad families of distributions and reduce a high-value sparse direction to a bounded-radius set in the graph of large correlations and searches the resulting candidate supports.

Giannis Iakovidis, Ankit Pensia · 0 citations
Preprint Sep 2026

Large solution-free sets via combinatorial degenerations

Consider the linear form $L(x,y,z,w) = 3x+y-2z-2w$. For a positive integer $N$, denote by $r_L(N)$ the largest size of a subset of $\{1,2,\dots,N\}$ that avoids nontrivial solutions to $L = 0$. We show that $r_L(N) = \Omega(N^{0.5608687})$, improving the lower bound for Problem 16 in Green's list of open problems. Our...

Paul Hametner, J. Solymosi · 0 citations
Preprint Sep 2026

Saddle-Point Problems with a Low-Dimensional Block Do Not Need Accurate Inner Solves

The method, certificate transport, keeps a strongly convex lower model of a single slice and uses it as a prior for a short accelerated run on the next slice and shows that the inner problems need not be solved accurately.

И. Ф. Фомин, A. Gasnikov · 0 citations
Preprint Sep 2026

A stochastic subgradient method with optimal failure exponent

Fix a target accuracy $\varepsilon$, a gradient-noise level $s$, and a horizon $N$. We wish to design algorithms which minimize the probability of observing a suboptimality gap which exceeds the target accuracy, i.e., $\mathcal{E}_N = -\log \sup_{f,P} \mathbb{P}_P(f(x_A) - f_\star \ge \varepsilon)$, with the noise law...

B. V. Van Parys · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.