Paper 2026/1406

An $n^{n+o(n)}$-Time Algorithm for the Lattice Isomorphism Problem

Abstract

The Lattice Isomorphism Problem asks whether two given lattices $\mathcal L_1$ and $\mathcal L_2$ are related by an orthogonal linear transformation. Haviv and Regev gave a seminal $n^{O(n)}$-time algorithm for this problem based on an isolation lemma (SODA 2014). We give algorithms for the decision, search, and all-isomorphisms versions of the problem running in time $n^{n+o(n)}$ times a polynomial in the input size. The main new ingredient is a Gaussian heat argument over convex bodies generated by shortest vectors: for $w\sim D_{\mathcal L^*,s}$, the vector $w$ canonically determines $n-o(n)$ independent shortest vectors, leaving a residual instance of rank $o(n)$. The remaining residual dimensions are handled by an $n^{o(n)}$-time canonicalizer obtained by adapting the Haviv-Regev algorithm. We then combine this canonicalizer with a birthday argument to recover all isomorphisms. For the all-isomorphisms version, this bound is asymptotically optimal in the worst case up to an $n^{o(n)}$ factor. As an extension, we also give, in the QRAM model, a quantum variant running in time $n^{\frac{2}{3}n+o(n)}$. It outputs a representative isomorphism together with generators for the automorphism group, thereby providing a compact description of the entire isomorphism coset.