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: 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
-
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}
}
