Polynomial reduction links linear code equivalence search to decision problem
A search-to-decision reduction for the linear code equivalence problem
Computational Complexity
Summary
Some mathematical codes can be transformed into each other through certain linear operations, but finding the exact transformation is a tough problem. The authors show a method to turn the problem of finding such a transformation into a simpler yes-or-no question, and then use answers to that question to recover the transformation itself. This makes solving the code equivalence problem easier by breaking it down into more manageable steps that only require checking if two codes are equivalent. Their approach works in polynomial time, meaning it remains efficient as the size of the codes grows.
What this means in practice
- •For cryptography engineers: Use polynomial-time reductions to better verify equivalence of linear codes, improving cryptanalysis tools for code-based cryptosystems.
- •For error correction code designers: Employ the reduction to simplify testing if two linear codes are equivalent, aiding code comparison and classification efforts.
A theory result. No direct application yet.
Authors
Jean-François Biasse, Giacomo Micheli, Benjamin Prada, Philip Waitkevich
Abstract
We present a polynomial-time reduction from the search variant of the linear code equivalence problem (i.e. the search for a linear isometry between the inputs) to its decisional variant. More precisely, given two linearly equivalent codes $\mathcal C_1,\mathcal C_2 \subseteq \mathbb{F}_q^n$, we show how to recover a linear isometry between them by making a polynomial number of queries to an oracle for decisional linear code equivalence. First, we prove that search-Permutation Code Equivalence (search-PCE -- the problem of finding a permutation $π\in\mathcal S_n$ mapping $\mathcal C_1$ to $\mathcal C_2$) reduces in polynomial time to PCE (i.e. the problem of deciding if there is a permutation map from $\mathcal C_1$ to $\mathcal C_2$) via at most $n^2$ oracle calls on instances of dimension $k$ and length at most $n^2(n+1)/2$. We then extend this approach to linearly equivalent codes: we recover the permutation part of a linear isometry via at most $n^2$ calls to a Linear Code Equivalence (LCE) oracle on instances of the same size, and we give a deterministic polynomial-time algorithm to recover the diagonal part once this permutation is known. Altogether, this yields a polynomial-time procedure to recover a linear isometry from an oracle for decisional LCE. From a linear-algebraic perspective, our results provide an explicit reconstruction of a monomial equivalence between two matrix representations from oracle access to the corresponding orbit membership problem.