The Closure of LCD-to-GI Reductions via Generalized Inner Products
Keita Ishizuka · 2026
Read The Closure of LCD-to-GI Reductions via Generalized Inner Products by Keita Ishizuka (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-23120.txt.
Introduction
Ishizuka asks whether the reduction from permutation equivalence of complementary dual codes to isomorphism extends to a nondegenerate symmetric bilinear form M. He defines what it takes for M to yield a reduction. He proves that for length at least three and field size, this holds when M is permutation invariant. The reduction then goes beyond LCD codes to codes with 1D hull. These are codes whose hull is spanned by a vector having nonzero coordinate sum. He counts these codes exactly and gives a polynomial time reduction algorithm.
Catalog record
| CREATOR | Keita Ishizuka |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58811 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.23120
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Closure of LCD-to-GI Reductions via Generalized Inner Products Keita Ishizuka Abstract 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 = a I + b J 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 1 with an explicit condition on the hull vector; in characteristic 2 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. Keywords: Permutation Equivalence Problem, Graph Isomorphism, LCD codes, Enumeration 1 Introduction The Permutation Equivalence Problem (PEP) for linear codes asks whether two given codes are identical up to a coordinate permutation. In coding theory, PEP underlies the classification of linear codes, a long-standing problem for which Sendrier’s Support Splitting Algorithm [ 11 ] remains the standard computational tool. In cryptography, the conjectured hardness of PEP and its close variants underlies a growing family of code-based signature schemes. The NIST PQC candidate LESS [ 4 ] originally relied on PEP and now uses the closely related Linear Equivalence Problem (LEP); the recent SPECK [ 2 ] is based on the Permutation Equivalence of Codes and Kernels (PECK) problem, which combines features of PEP and the Permuted Kernel Problem (PKP) and reduces to PEP in the high- q regime, where the scheme draws hard instances from codes with large hull. Understanding the structural and computational boundaries of PEP therefore has direct implications for both code classification and post-quantum cryptography. The complexity of PEP is closely tied to that of Graph Isomorphism (GI). Petrank and Roth [ 10 ] showed that PEP is at least as hard as GI; conversely, Bardet et al. [ 3 ] proved that PEP for Linear Complementary Dual (LCD) codes (those with trivial hull \Hull(C)=C\cap C^{\perp}=\{0\} ) reduces to GI in polynomial time. Their construction maps each LCD code to a weighted graph via the orthogonal projector \Pi_{C}=G^{T}(GG^{T})^{-1}G , with the property that two LCD codes are permutation-equivalent if and only if their projectors are isomorphic as weighted graphs. Combined with Babai’s quasi-polynomial-time algorithm for GI [ 1 ] , this yields a sub-exponential algorithm for PEP on LCD instances. However, the construction requires GG^{T} to be nonsingular, ruling out codes with nontrivial hull. The natural question is: how far can the orthogonal projector method be pushed? Our contribution. We answer this question completely. First, we prove that the orthogonal projector \Pi_{C,M}=MG^{T}(GMG^{T})^{-1}G gives a valid reduction ( C_{1}\cong C_{2}\Leftrightarrow\Pi_{C_{1},M}\cong\Pi_{C_{2},M} ) if and only if M=aI+bJ (Theorem 3.5 ). Second, we characterize exactly which codes are reducible: a code admits such a reduction if and only if its hull dimension is at most 1 with (x,\mathbf{1})\neq 0 for the hull vector x (Theorem 4.5 ); in characteristic 2 , only LCD codes are reducible (Corollary 4.6 ). Together, these results establish the closure of the orthogonal projector approach: codes with hull dimension \geq 2 are provably beyond its reach, regardless of the choice of nondegenerate symmetric bilinear form. We also derive exact enumeration formulas using Weil’s theorem on quadratic forms (Theorem 5.3 ) and provide a polynomial-time reduction algorithm (Section 6 ). Relation to prior work. A preliminary 3-page poster by the author [ 6 ] introduced the family of permutation-invariant bilinear forms with structure matrix aI+bJ and established the dimension bound |\dim\Hull_{M}(C)-\dim\Hull(C)|\leq 1 . That work used these tools to accelerate the Support Splitting Algorithm [ 11 ] . The present paper shares only this characterization and dimension bound with the poster (Lemma 3.3 and Theorem 4.2 ), reproduced here for self-containment. The main results of this paper address the distinct question of GI-reducibility and are not present in [ 6 ] . Organization. Section 2 reviews definitions and basic properties. Section 3 introduces permutation-invariant bilinear forms and characterizes valid structure matrices. Section 4 characterizes GI-reducible codes and proves the closure result. Section 5 derives enumeration formulas. Section 6 presents the reduction algorithm. Section 7 concludes with open questions. Appendix A collects standard LCD code enumeration formulas (Carlet et al.), and Appendix B extends them to the type- \epsilon setting needed in Section 5 . 2 Preliminaries Let S_{n} denote the symmetric group on n elements. For \pi\in S_{n} and a vector x=(x_{1},\ldots,x_{n})\in\mathbb{F}_{q}^{n} , we define \pi(x)=(x_{\pi^{-1}(1)},\ldots,x_{\pi^{-1}(n)}) . The corresponding permutation matrix P_{\pi}\in\mathbb{F}_{q}^{n\times n} is defined by (P_{\pi})_{ij}=1 if j=\pi(i) and 0 otherwise, so that \pi(x)=xP_{\pi} for row vectors. 2.1 Graphs In this paper, we consider directed graphs with self-loops and edge weights in \mathbb{F}_{q} . A directed graph on n vertices is represented by a matrix A\in\mathbb{F}_{q}^{n\times n} where A_{ij} denotes the weight of the directed edge from vertex i to vertex j . Self-loops are allowed ( A_{ii} may be nonzero). An undirected graph is the special case where the adjacency matrix A is symmetric. Two graphs with adjacency matrices A_{1},A_{2}\in\mathbb{F}_{q}^{n\times n} are isomorphic if there exists a permutation \pi\in S_{n} such that A_{2}=P_{\pi}^{T}A_{1}P_{\pi} , where P_{\pi} is the permutation matrix corresponding to \pi . Definition 2.1 (Graph Isomorphism Problem) . Given adjacency matrices A_{1} and A_{2} of two graphs, decide whether there exists a permutation \pi\in S_{n} such that A_{2}=P_{\pi}^{T}A_{1}P_{\pi} . It is well known that directed graph isomorphism reduces to undirected graph isomorphism in polynomial time (by a standard gadget construction), and that edge weights can be eliminated in polynomial time by replacing each weighted edge with a gadget encoding the weight. Babai [ 1 ] showed that GI can be solved in quasipolynomial time 2^{O(\log^{c}n)} for some constant c . Combined with the above reductions, directed graph isomorphism can also be solved in quasipolynomial time. 2.2 Linear Codes Let \mathbb{F}_{q} denote the finite field of order q , where q=p^{m} for some prime p and positive integer m . The characteristic of \mathbb{F}_{q} is p . We denote by \mathbb{F}_{q}^{n} the n -dimensional vector space over \mathbb{F}_{q} . An [n,k]_{q} code is a k -dimensional subspace of \mathbb{F}_{q}^{n} . The values n and k are called length and dimension, respectively. A generator matrix of a code C is a k\times n matrix G whose rows form a basis of C . For vectors v_{1},\ldots,v_{m}\in\mathbb{F}_{q}^{n} , we denote by \langle v_{1},\ldots,v_{m}\rangle the subspace spanned by these vectors. Two codes C_{1} and C_{2} of length n over \mathbb{F}_{q} are permutation-equivalent if there exists \pi\in S_{n} such that C_{2}=C_{1}P_{\pi} , where P_{\pi} is the permutation matrix corresponding to \pi . Definition 2.2 (Permutation Equivalence Problem) . Given two [n,k]_{q} codes C_{1} and C_{2} , decide whether there exists a permutation \pi\in S_{n} such that C_{2}=C_{1}P_{\pi} . The standard inner product on \mathbb{F}_{q}^{n} is defined as \langle x,y\rangle=\sum_{i=1}^{n}x_{i}y_{i} for x=(x_{1},\ldots,x_{n}) and y=(y_{1},\ldots,y_{n}) in \mathbb{F}_{q}^{n} . The dual code of C with respect to the standard inner product is C^{\perp}=\{y\in\mathbb{F}_{q}^{n}:\langle x,y\rangle=0\text{ for all }x\in C\} . If C is an