{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreibiunmt7aa5jqxyzpcayrymjs65ir5ijtuwnivy4pseuyymgg2t3u",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mokskbf3ey42"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.18662v1",
  "publishedAt": "2026-06-18T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Huck Bennett",
    "Kyle Fridberg"
  ],
  "textContent": "**Authors:** Huck Bennett, Kyle Fridberg\n\nA 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 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 $\\cal{L} \\subset \\mathbb{R}^n$: (1) every such lattice $\\cal{L}$ is isomorphic to $\\cal{L}_0 \\oplus \\mathbb{Z}^r$ for some self-dual lattice $\\cal{L}_0$ with $λ_1(\\cal{L}_0)^2 \\geq 2$, and (2) every such lattice $\\cal{L}$ has \\emph{characteristic vectors}, i.e., there exist vectors $\\mathbf{w} \\in \\cal{L}$ such that for every $\\mathbf{v} \\in \\cal{L}$, $\\langle\\mathbf{v}, \\mathbf{w}\\rangle \\equiv \\langle\\mathbf{v}, \\mathbf{v}\\rangle \\pmod{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.",
  "title": "On (Non-)Isomorphism of Self-Dual Lattices and Codes"
}