Relating Code Equivalence to Other Isomorphism Problems

Huck Bennett; Kaung Myat Htay Win

Paper 2024/782

Relating Code Equivalence to Other Isomorphism Problems

Huck Bennett, University of Colorado Boulder

Kaung Myat Htay Win, Oregon State University

Abstract

We study the complexity of the Code Equivalence Problem on linear error-correcting codes by relating its variants to isomorphism problems on other discrete structures---graphs, lattices, and matroids. Our main results are a fine-grained reduction from the Graph Isomorphism Problem to the Linear Code Equivalence Problem over any field $F$ , and a reduction from the Linear Code Equivalence Problem over any field $F_{p}$ of prime, polynomially bounded order $p$ to the Lattice Isomorphism Problem. Both of these reductions are simple and natural. We also give reductions between variants of the Code Equivalence Problem, and study the relationship between isomorphism problems on codes and linear matroids.

Note: Addressed reviewer comments, added an example, and added citations.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Designs, Codes, and Cryptography
Keywords: Code Equivalence Problem Reductions Lattice Isomorphism Problem Graph Isomorphism Problem
Contact author(s): huck bennett @ colorado edu
htaywink @ oregonstate edu
History: 2024-12-15: last of 2 revisions; 2024-05-21: received; See all versions
Short URL: https://ia.cr/2024/782
License: CC BY

BibTeX

@misc{cryptoeprint:2024/782,
      author = {Huck Bennett and Kaung Myat Htay Win},
      title = {Relating Code Equivalence to Other Isomorphism Problems},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/782},
      year = {2024},
      url = {https://eprint.iacr.org/2024/782}
}