Paper 2024/782
Relating Code Equivalence to Other Isomorphism Problems
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: 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 ProblemReductionsLattice Isomorphism ProblemGraph 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}
}
