Code equivalence links to automorphism group problems for error correcting codes
Code Equivalence and Automorphism Problems for Codes
Computational Complexity
Summary
Sometimes, we need to tell if two error-correcting codes are basically the same, just arranged differently. This paper shows that figuring this out is just as hard as certain problems about the symmetries of these codes. The authors connect these problems through ways that let one solution quickly turn into another, for any kind of linear code. This helps understand and organize code comparison and symmetry problems as one set of related challenges.
What this means in practice
- •For coding engineers: Confirm code equivalence by computing code automorphism structures, enabling streamlined code analysis in communication systems.
- •For cryptography developers: Assess cryptosystem security by translating code symmetry problems into automorphism computations for advanced code-based cryptography.
A theory result. No direct application yet.
Authors
Jean-Francois Biasse, Alexandra V. Hostetler, Anuvrat Jaindungarwal
Abstract
We study the complexity of the Code Equivalence problem and show that it is polynomially equivalent to several computational automorphism problems for codes. These problems ask for the cardinality (ACOUNT), an orbit partition (APART), and a generating set (AGEN) for the permutation automorphism group of a code. We present deterministic, polynomial-time reductions between Permutation Code Equivalence (PCE) and each of these problems, including a one-shot reduction from search-PCE to AGEN that makes a single oracle call. We present similar reductions between Linear Code Equivalence (LCE) and analogous problems for the monomial automorphism group of a code. All of our reductions work for any linear codes.