The Closure of LCD-to-GI Reductions via Generalized Inner Products

Technical Summary: The Closure of LCD-to-GI Reductions via Generalized Inner Products

1. Problem Statement

The Permutation Equivalence Problem (PEP) for linear codes asks whether two given linear codes are identical up to a coordinate permutation. This problem is fundamental to both the classification of linear codes and the security analysis of code-based cryptography (e.g., the LESS signature scheme and the SPECK scheme).

The complexity of PEP is closely tied to the Graph Isomorphism (GI) problem. While PEP is generally considered hard, a significant breakthrough by Bardet et al. [3] demonstrated that PEP for Linear Complementary Dual (LCD) codes (codes with a trivial hull, i.e., $C \cap C^\perp = \{0\}$) reduces to GI in polynomial time. This reduction maps an LCD code to a weighted graph via its orthogonal projector $\Pi_C = G^T(GG^T)^{-1}G$.

However, this method relies on the Gram matrix $GG^T$ being nonsingular, which restricts its applicability to LCD codes. Codes with non-trivial hulls (where $\dim(\text{Hull}(C)) \ge 1$) cannot be processed by this specific construction. The central question addressed in this paper is: How far can the orthogonal projector method be extended? Specifically, can it be generalized to codes with non-trivial hulls by using a different bilinear form, and if so, what are the precise structural limits of such a reduction?

2. Methodology

The authors generalize the standard inner product to arbitrary nondegenerate symmetric bilinear forms represented by a structure matrix $M$.

• Generalized Projectors: They define an $M$-dual code $C^{\perp_M}$ and an $M$-hull $\text{Hull}_M(C)$. For an $M$-LCD code (where $\text{Hull}_M(C) = \{0\}$), they construct a generalized orthogonal projector:
  $$\Pi_{C,M} = M G^T (G M G^T)^{-1} G$$
• Reduction Condition: The core of the reduction relies on the identity $\Pi_{CP, M} = P^T \Pi_{C,M} P$, where $P$ is a permutation matrix. This identity ensures that if two codes are permutation-equivalent, their projectors are isomorphic as weighted graphs.
• Characterization of $M$: The authors investigate which structure matrices $M$ satisfy the condition that $P M P^T = M$ (or a scalar multiple thereof) for all permutations $P$. This is necessary to ensure the projector behaves correctly under permutation.
• Enumeration and Algorithms: Using character sums over quadratic forms (specifically Weil's theorem), the authors derive exact enumeration formulas for the number of reducible codes. They also construct a polynomial-time algorithm that attempts to find a suitable $M$ to reduce a given pair of codes to GI.

3. Key Contributions and Results

A. Characterization of Valid Structure Matrices (Theorem 3.5)
The paper proves that the orthogonal projector method yields a valid reduction ($C_1 \cong C_2 \iff \Pi_{C_1, M} \cong \Pi_{C_2, M}$) if and only if the structure matrix $M$ has the form:
$$M = aI + bJ$$
where $I$ is the identity matrix, $J$ is the all-ones matrix, and $a, b \in \mathbb{F}_q$ satisfy non-degeneracy conditions ($a \neq 0$ and $a + nb \neq 0$). No other nondegenerate symmetric bilinear form allows for this reduction. This establishes the closure of the orthogonal projector approach: one cannot extend the method by choosing arbitrary bilinear forms; the form must be a linear combination of the identity and the all-ones matrix.

B. Complete Characterization of Reducible Codes (Theorem 4.5)
The authors determine exactly which codes admit such a reduction:

• A code $C$ is GI-reducible via this method if and only if:
  1. $C$ is an LCD code (standard case, $M=I$), OR
  2. $\dim(\text{Hull}(C)) = 1$ and the unique hull vector $x$ satisfies $(x, \mathbf{1}) \neq 0$ (where $\mathbf{1}$ is the all-ones vector).
• Characteristic 2: In fields of characteristic 2, the condition $(x, \mathbf{1}) \neq 0$ is impossible for any vector in the hull (since $(x, x) = (x, \mathbf{1})^2 = 0$ implies $(x, \mathbf{1}) = 0$). Consequently, only LCD codes are reducible in characteristic 2.
• Impossibility for Higher Hulls: Codes with $\dim(\text{Hull}(C)) \ge 2$ are provably not reducible via the orthogonal projector method, regardless of the choice of $M = aI + bJ$.

C. Enumeration Formulas (Theorem 5.3)
The paper provides exact formulas for counting the number of GI-reducible $[n, k]_q$ codes (for odd $q$). The count is the sum of:

1. The number of standard LCD codes, $L(n, k, q)$.
2. The number of codes with hull dimension 1 satisfying the coordinate sum condition, derived using the count of isotropic vectors with non-zero coordinate sums and the mass formulas for LCD codes over quotient spaces with specific discriminants.

D. Reduction Algorithm (Section 6)
A polynomial-time algorithm is presented:

1. Check hull dimensions. If $\ge 2$, output "not GI-reducible."
2. If LCD, use $M=I$.
3. If hull dimension is 1, search for a scalar $b$ such that $M = I + bJ$ makes both codes $M$-LCD.
4. Construct the generalized projectors and solve the resulting Graph Isomorphism problem.

4. Significance and Claims

The paper claims to provide a complete characterization of the orthogonal projector method's capabilities.

• Closure: It definitively closes the door on extending the Bardet et al. reduction to codes with large hulls ($\ge 2$) using this specific technique. It proves that the method is inherently limited to codes with hull dimension at most 1 (and only LCD codes in characteristic 2).
• Structural Limits: It identifies the specific algebraic structure ($M = aI + bJ$) required for the reduction to work, showing that no other symmetric bilinear forms can facilitate this mapping.
• Cryptographic Implications: The results offer a criterion for selecting parameters in code-based cryptographic schemes (like SPECK) to ensure they possess hull dimensions $\ge 2$, thereby placing them beyond the reach of this specific GI-reduction attack vector.

The authors conclude by posing an open question: whether other reduction strategies (not based on orthogonal projectors) exist that can map PEP for codes with $\dim(\text{Hull}(C)) \ge 2$ to GI, or if such reductions are provably impossible.