The Closure of LCD-to-GI Reductions via Generalized Inner Products
For coding theorists and cryptographers, this work incrementally extends the known reduction from LCD codes to GI to a slightly broader class of codes, but remains limited to codes with small hull.
The paper extends a reduction from Permutation Equivalence Problem (PEP) for LCD codes to Graph Isomorphism (GI) to codes with hull dimension at most 1, proving closure of the orthogonal projector method. It provides exact enumeration formulas and a polynomial-time reduction algorithm.
The Permutation Equivalence Problem (PEP) for linear codes is a fundamental problem in coding theory and cryptography. A recent reduction shows that PEP for Linear Complementary Dual (LCD) codes reduces to Graph Isomorphism (GI) via orthogonal projectors, but is restricted to codes with trivial hull. We prove that this approach extends to bilinear forms $M = aI + bJ$, and that no other nondegenerate symmetric form yields a valid reduction. A code is reducible if and only if its hull dimension is at most $1$ with an explicit condition on the hull vector; in characteristic $2$, only LCD codes are reducible. This establishes the closure of the orthogonal projector method. We derive exact enumeration formulas via character sums over quadratic forms and provide a polynomial-time reduction algorithm.