Shortest LCD embeddings of binary, ternary and quaternary linear codes

Problem Statement
Linear codes with complementary duals (LCD codes) are a significant area of research in coding theory and cryptography, particularly due to their resistance to side-channel and fault injection attacks. While it is known that every linear code over $\mathbb{F}_q$ ($q \ge 4$) is equivalent to an LCD code, and similar results exist for $\mathbb{F}_{q^2}$, the bounds for minimum distances of LCD codes over $\mathbb{F}_2$, $\mathbb{F}_3$, and Hermitian LCD codes over $\mathbb{F}_4$ remain unknown for many lengths and dimensions. A central challenge in coding theory is determining the largest minimum distance for a given length and dimension. This paper addresses the specific problem of embedding arbitrary linear codes into LCD codes, aiming to find the "shortest" such embedding (minimal length increase) and utilizing this method to construct new distance-optimal LCD codes.

Methodology
The authors introduce a systematic approach to embed a given linear code $C$ into an LCD code $\tilde{C}$ by adding the minimum number of columns to its generator matrix. The methodology proceeds as follows:

1. Theoretical Foundation: The paper establishes that the minimum number of columns ($m$) required to embed an $[n, k]$ code $C$ into an LCD code is exactly equal to the dimension $\ell$ of the hull of $C$ (where $\text{Hull}(C) = C \cap C^\perp$). Consequently, the length of the shortest LCD embedding is $n + \ell$.
2. Structural Characterization: The authors characterize the generator matrix of a shortest LCD embedding. If $G$ is a generator matrix of $C$ decomposed into a part generating the hull, $G(\text{Hull}(C))$, and a remaining part $A$, then a shortest LCD embedding is generated by a matrix of the form:
   $$\tilde{G} = \begin{bmatrix} G(\text{Hull}(C)) & D \\ A & C \end{bmatrix}$$
   where $D$ is an invertible $\ell \times \ell$ matrix and $C$ is an arbitrary $(k-\ell) \times \ell$ matrix. The paper proves that appending an invertible matrix to the rows corresponding to the hull and an arbitrary matrix to the remaining rows always yields a shortest LCD embedding.
3. Construction Strategy: The authors apply this embedding method to known distance-optimal linear codes (specifically ternary and quaternary codes) that are not themselves LCD. By calculating the hull dimension of these existing codes and appending the necessary columns according to the derived structure, they generate new LCD codes.

Key Contributions and Results
The paper provides both theoretical bounds and concrete constructions:

• Theoretical Results:

  • Proves that the length of the shortest LCD embedding of an $[n, k]$ code with hull dimension $\ell$ is $n + \ell$.
  • Characterizes all possible forms of generator matrices for these shortest embeddings, showing they are equivalent to appending an invertible matrix to the hull-generating rows.
  • Demonstrates that the length of the shortest LCD embedding of a code $C$ is identical to that of its hull, $\text{Hull}(C)$.

• New Code Constructions:
  Using the shortest LCD embedding method on existing linear codes, the authors constructed several new LCD codes with parameters that improve upon the known minimum distances:

  • Ternary LCD Codes:
    • $[23, 4, 14]$: Improves the known minimum distance from 13 to 14.
    • $[23, 5, 12]$: Improves the known minimum distance from 11 to 12.
    • $[24, 6, 12]$: Improves the known minimum distance from 11 to 12.
    • $[25, 5, 14]$: Improves the known minimum distance from 13 to 14.
  • Quaternary Hermitian LCD Code:
    • $[21, 10, 8]$: Improves the known minimum distance from 7 to 8.

The authors note that for the new parameters $[23, 4, 14]$ and $[23, 5, 12]$, they found 226 and 38 inequivalent codes, respectively. These codes are distance-optimal and inequivalent to those currently in the BKLC (Best Known Linear Codes) database.

Significance
The paper claims that the shortest LCD embedding method is a useful tool for finding distance-optimal LCD codes over various fields. By determining the precise number of columns needed and characterizing their structure, the method provides a constructive pathway to improve the minimum distance of known linear codes when converted to LCD codes. The results demonstrate that this approach successfully yields new codes with minimum distances one greater than those of previously known codes for specific ternary and quaternary parameters.

Limitations and Future Directions
The authors acknowledge a limitation in their approach: since the search space for the appended invertible and arbitrary matrices is excessively large, it is difficult to guarantee finding the specific embedding that yields the absolute largest minimum distance for a given code. They suggest that future research should focus on developing methods to select the appended matrices more strategically to maximize the resulting minimum distance or to determine if the appended matrices can be further restricted up to equivalence to reduce the search space.