On (Non-)Isomorphism of Self-Dual Lattices and Codes (opens in new tab)

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 $\cal{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 ZLI...