🔢 mathematics

Binary Caps and LCD Codes with Large Dimensions

This paper establishes a connection between LCD codes and caps in projective space to derive computation-free nonexistence theorems for LCD codes with minimum distance at least 4, thereby determining the optimal minimum distances for codimensions 7 and 8 for the first time.

Original authors: Keita Ishizuka, Yuhi Kamio

Published 2026-04-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Keita Ishizuka, Yuhi Kamio

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Building Unbreakable Digital Locks

Imagine you are a master locksmith trying to build the most secure digital vaults possible. In the world of computer science, these "vaults" are called codes. Specifically, this paper is about a special type of code called an LCD code (Linear Complementary Dual).

Think of an LCD code as a secret handshake. To be an LCD code, the secret handshake must be so unique that if you try to combine it with its "mirror image" (its dual code), they cancel each other out completely, leaving nothing behind. This property makes these codes incredibly useful for protecting computers from hackers who try to steal secrets by watching how much electricity the computer uses (side-channel attacks).

The goal of the researchers (Ishizuka and Kamio) was to answer a simple question: "How far apart can we make the valid messages in these vaults so that even if a few letters get scrambled by noise, we can still fix them?" This distance is called the minimum distance. The bigger the distance, the stronger the vault.

The Problem: The "Exhaustive Search" Bottleneck

For a long time, mathematicians knew how to build these strong vaults for small sizes. But as the vaults got bigger (specifically, when the "codimension" or the amount of extra security space increased to 6, 7, or 8), the problem became a nightmare.

Previously, to prove that a certain strong vault couldn't be built, researchers had to use supercomputers to check every single possible combination, one by one. It was like trying to find a needle in a haystack by pulling out every single piece of hay and checking it.

For codimension 6, they found a weird pattern: sometimes a strong vault was possible, sometimes not, depending on whether the size was an odd or even number.
But they couldn't prove why this pattern existed without running those massive, slow computer searches.
For codimensions 7 and 8, the haystack was so huge that the computers simply couldn't finish the job. The answers were unknown.

The New Approach: Geometry and "Caps"

The authors decided to stop counting haystacks and start looking at the shape of the hay. They realized that building these codes is actually the same as arranging points in a special kind of geometric space (called Projective Space).

Here is the analogy:

The Code: A collection of points.
The Rule: No three points can ever line up in a straight line.
The Shape: In geometry, a collection of points where no three are in a line is called a Cap. (Think of a "cap" as a hat that covers a group of points without letting any three sit in a row).

The researchers discovered a magical link: A code is an LCD code if and only if a specific mathematical "balance scale" (called a Gram Matrix) built from these points doesn't tip over. If the scale is balanced (nonsingular), the code is secure. If it tips, the code fails.

The Breakthrough: The "Big Hat" Theory

Using a deep theory about the largest possible "Caps" (developed by mathematicians Bruen and Wehlau), the authors found a hidden rule about the shape of these point collections.

They proved that if you try to build a very large, secure LCD code (with a minimum distance of 4 or more), the points must fit inside a very specific, rigid shape. It's like trying to fit a giant crowd into a room; if the crowd is too big, they must stand in a specific formation, or they simply won't fit.

This geometric constraint led to two major discoveries:

The "Odd/Even" Rule: They proved mathematically that for these large codes, the size of the code must match the parity (odd/even nature) of the security level. This explained the alternating pattern seen in the computer searches without needing to run a single search.
The Size Limit: They proved there is a hard ceiling on how big these codes can be. If you try to make them bigger than this limit, they simply cannot exist.

The Results: Solving the Mystery

By applying these geometric rules, the authors achieved three things:

Computation-Free Proof: They proved that for codimension 6, certain code sizes are impossible. This replaced the need for the slow, brute-force computer searches with a clean, logical mathematical proof.
Solving Codimension 7: They completely mapped out the best possible security for codes of this size for every possible length. They found exactly where the "alternating pattern" stops and what the maximum security is.
Solving Codimension 8: They did the same for codimension 8, a problem that was previously considered too hard for computers to solve. They determined the exact maximum security for every single code length in this category.

Why This Matters

Before this paper, if you wanted to know the best security for a specific large code, you might have to wait for a supercomputer to run for weeks, or you might just have to guess.

Now, thanks to this "geometric lens," we have a clear map. We know exactly how big and strong these digital vaults can be, and we know exactly why they can't be any bigger. It turns a chaotic puzzle of millions of possibilities into a neat, understandable geometric shape.

In short: The authors stopped trying to count every grain of sand on the beach and instead figured out the shape of the beach itself. This allowed them to predict exactly where the sand can and cannot be, solving a mystery that had stumped computers for years.

1. Problem Statement

The paper addresses the fundamental problem of determining the largest minimum distance, denoted as $d^E_2(n, k)$ , among all binary Linear Complementary Dual (LCD) $[n, k]$ codes.

Context: LCD codes are crucial in cryptography for resisting side-channel and fault injection attacks. While it is known that any code over $\mathbb{F}_q$ ( $q \ge 4$ ) is equivalent to an LCD code, binary and ternary LCD codes impose genuine structural constraints.
Specific Challenge: Previous research had determined $d^E_2(n, k)$ for small dimensions ( $k \le 5$ ) and small codimensions ( $m = n-k \le 5$ ). However, for larger codimensions ( $m \ge 6$ ), determining the optimal minimum distance for $d \ge 4$ became a bottleneck.
The Gap: Existing methods relied on Hamming codes (which ensure 2-independence of columns) to analyze $d \ge 3$ . These methods fail for $d \ge 4$ , which requires 3-independence (no three columns are linearly dependent). Consequently, determining $d^E_2(n, n-m)$ for $m \ge 6$ previously required exhaustive computational searches, which are infeasible for large $n$ . Specifically, the behavior of $d^E_2(n, n-6)$ showed an alternating pattern based on the parity of $n$ , but lacked a theoretical explanation.

2. Methodology

The authors establish a novel connection between the algebraic properties of LCD codes and the geometric properties of caps in projective spaces.

Geometric Translation:
- An $[n, k, d]$ code with $d \ge 4$ corresponds to a set of points $S$ in the projective space $PG(m-1, 2)$ (where $m=n-k$ ) such that no three points are collinear. Such a set $S$ is called a cap.
- The code $C_S$ generated by a cap $S$ is LCD if and only if its associated Gram matrix $U_S = \sum_{s \in S} ss^T$ is nonsingular (invertible) over $\mathbb{F}_2$ .
Structural Analysis of Large Caps:
- The authors utilize the structure theory of maximal caps developed by Bruen and Wehlau. This theory classifies large caps based on their "period" (a subspace of vectors $v$ such that $S+v = S$ ).
- They analyze the rank of the Gram matrix $U_S$ relative to the period structure of the cap.
Key Theoretical Derivation:
- They prove that sufficiently large caps with a nonsingular Gram matrix must be contained within a specific geometric structure: the complement of a hyperplane ( $\mathbb{F}_2^m \setminus \langle v \rangle^\perp$ ).
- This geometric constraint imposes strict limitations on the size ( $n$ ) and parity of the code length relative to the codimension ( $m$ ).

3. Key Contributions

LCD Characterization via Caps: The paper provides a necessary and sufficient condition for a code derived from a cap to be LCD: the matrix $U_S = \sum_{s \in S} ss^T$ must be nonsingular. This transforms an algebraic coding problem into a geometric question about point configurations.
Structure Theorem for Large Caps (Theorem 12): The authors establish a sufficient condition for large caps to lie in hyperplane complements. Specifically, if a cap $S$ is large enough ( $|S| \ge 2^{m-2} + 2^{m-4} - \text{rank}(U_S) + 1$ ), it must be a subset of $\mathbb{F}_2^m \setminus \langle v \rangle^\perp$ .
Nonexistence Theorems (Theorems 13 & 17): By combining the structure theorem with the nonsingularity requirement, they prove that for codimensions $m \ge 4$ $m \geq 4$ , any LCD $[n, n-m]$ $[n, n - m]$ code with minimum distance $d \ge 4$ $d \geq 4$ must satisfy:
- Parity Constraint: $n \equiv m \pmod 2$ (The length and codimension must have the same parity).
- Size Constraint: $n \le 2^{m-1} - m$ .
Computation-Free Proofs: These theorems provide rigorous, non-computational proofs for nonexistence results that were previously only verified via brute-force search.

4. Main Results

The framework allows the authors to completely determine the optimal minimum distances for codimensions $m=6, 7,$ and $8$.

Codimension 6 ( $m=6$ ):
- Proves that LCD $[n, n-6, 4]$ codes do not exist for odd $n$ in the range $17 \le n \le 26$ .
- This explains the previously observed alternating pattern between $d=3$ and $d=4$ without exhaustive search.
Codimension 7 ( $m=7$ ):
- Completely determines $d^E_2(n, n-7)$ for all $n$ .
- Result: For $n \ge 34$ , $d^E_2(n, n-7) = 4$ if $n$ is odd, and $d^E_2(n, n-7) = 3$ if $n$ is even (for $n$ in specific ranges). For very large $n$ , the distance drops to 2.
Codimension 8 ( $m=8$ ):
- Completely determines $d^E_2(n, n-8)$ for all $n$ .
- Result: For $n \ge 73$ , LCD codes with $d \ge 4$ only exist if $n$ is even and $n \le 120$ . For odd $n \ge 73$ , the maximum distance is 3. For $n \ge 248$ , the distance is 2.

5. Significance

Theoretical Breakthrough: This is the first theoretical framework that explains the "alternating pattern" in optimal LCD code distances based on the parity of $n$ . It moves the field from reliance on computational enumeration to structural geometric proofs.
Scalability: The method extends the determination of optimal distances to codimensions ( $m=7, 8$ ) where exhaustive search was computationally infeasible.
Limitations and Future Work: The approach relies heavily on the classification of caps in binary projective spaces ( $q=2$ ) by Bruen and Wehlau. The authors note that this does not directly extend to ternary ( $q=3$ ) or higher fields, as the detailed classification of large caps for $q > 2$ is not yet available. Future work is needed to develop geometric frameworks for nonbinary LCD codes and to extend these results to $m \ge 9$ .

In summary, the paper successfully bridges finite geometry and coding theory to resolve open problems regarding the limits of binary LCD codes, providing a unified, computation-free explanation for their structural constraints.