Abstract
Recent work motivated by cryptographic applications has studied the complexity of the Lattice Isomorphism Problem (LIP). In this work, we investigate LIP on self-dual lattices $\mathcal{L} \subset \mathbb{R}^n$, which naturally arise 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 by Bennett, Ganju, Peetathawachai, and Stephens-Davidowitz (Eurocrypt, 2023) and Ducas (Des. Codes Cryptogr., 2024). The latter result extends the $\mathsf{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 $\lambda_1(\mathcal{L}_0)^2 \geq 2$, and (2) every such lattice $\mathcal{L}$ has characteristic vectors, i.e., there exist vectors $\mathbf{w} \in \mathcal{L}$ such that for every $\mathbf{v} \in \mathcal{L}$, $\langle\mathbf{v}, \mathbf{w}\rangle \equiv \langle\mathbf{v}, \mathbf{v}\rangle \pmod{2}$.
Our results build on the work of 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, observing that similar structural properties imply a polynomial-time algorithm for PCE on certain such codes. This yields a natural class of codes with large hull for which PCE is easy.
Blogger's Review: This paper makes significant strides in the isomorphism problem of self-dual lattices and codes, particularly by introducing new algorithms and theoretical frameworks that advance lattice theory research in cryptographic applications. Future work will benefit from exploring algorithm optimization and expanding application scopes.