On (Non-)Isomorphism of Self-Dual Lattices and Codes

Abstract

A recent line of work motivated by cryptographic applications has studied the complexity of the Lattice Isomorphism Problem (LIP). In this work, we study LIP on self-dual lattices $\mathcal{L}\subset {\mathbb{R}}^n$, which appear naturally in many applications. Our main results are a $2^{n/2+o(n)}$-time randomized algorithm for LIP and a $\mathsf{coNP}$ protocol for LIP on a broad class of self-dual lattices. These results extend recent work on ZLIP, the problem of deciding whether a lattice is isomorphic to ${\mathbb{Z}}^n$. In particular, the former result extends the $2^{n/2+o(n)}$-time algorithms for ZLIP of Bennett, Ganju, Peetathawachai, and Stephens-Davidowitz (Eurocrypt, 2023) and of Ducas (Des. Codes Cryptogr., 2024). The latter result extends the $\mathrm{ZLIP}\in \mathsf{coNP}$ result of Hunkenschröder (Math. Prog. Series A, 2024). Our results leverage two key structural properties of self-dual lattices $\mathcal{L}\subset {\mathbb{R}}^n$: (1) every such lattice $\mathcal{L}$ is isomorphic to ${\mathcal{L}}_0\oplus {\mathbb{Z}}^r$ for some self-dual lattice ${\mathcal{L}}_0$ with $\hat{I}{»}_1({\mathcal{L}}_0{)}^2\ge 2$, and (2) every such lattice $\mathcal{L}$ has \emph{characteristic vectors}, i.e., there exist vectors $\mathbf{w}\in \mathcal{L}$ such that for every $\mathbf{v}\in \mathcal{L}$, $⟨\mathbf{v},\mathbf{w}⟩\equiv ⟨\mathbf{v},\mathbf{v}⟩(\mathrm{mod}2)$. Our results use a line of work by Elkies and Gaulter on lattices with long shortest characteristic vectors, and can be strengthened assuming a positive answer to a related question of Elkies (Math. Res. Lett., 1995). We also study Permutation Code Equivalence (PCE) on self-dual codes, and we observe that similar structural properties imply a polynomial-time algorithm for PCE on certain such codes. This gives a natural class of codes with large hull for which PCE is easy.