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 $\mathbb{F}$, and a reduction from the Linear Code Equivalence Problem over any field $\mathbb{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: Added citations and minor updates.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Code Equivalence ProblemReductionsLattice Isomorphism ProblemGraph Isomorphism Problem
Contact author(s)
huck bennett @ colorado edu
htaywink @ oregonstate edu
History
2024-05-28: revised
2024-05-21: received
See all versions
Short URL
https://ia.cr/2024/782
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2024/782}},
      url = {https://eprint.iacr.org/2024/782}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.