🔢 mathematics

A New Class of Linear Codes

This paper introduces a new class of linear codes constructed via multiplicative character sums and superelliptic curves that achieve exponential size over binary fields with relative distance asymptotic to 1/2, offer improved rate-distance trade-offs when concatenated with Reed-Solomon codes, and exhibit cryptographic potential due to their random-like square and decoding properties.

Original authors: Akash Bhople, Giacomo Cherubini, Giacomo Micheli, Tefjol Pllaha

Published 2026-06-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Akash Bhople, Giacomo Cherubini, Giacomo Micheli, Tefjol Pllaha

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

Imagine you are trying to send a secret message across a noisy telephone line. In the world of coding theory, this "message" is a string of numbers (a codeword), and the "noise" is errors that might flip some of those numbers. To make sure the message gets through, we need to make the codewords very different from each other. If two messages are too similar, a little bit of noise might make them look identical, and you won't know which one was sent.

The distance between two messages is how many spots they differ in. The rate is how much actual information you can pack into the message compared to the total length of the message.

This paper introduces a new, clever way to build these "secret message" codes. The authors, Akash Bhople and colleagues, have created a new class of linear codes (a specific, mathematically tidy type of code) that are significantly better than the best-known codes we had before, especially when we want the messages to be very distinct from one another.

Here is the breakdown of their discovery using simple analogies:

1. The "Shadow" Trick

The core of their invention is something they call a "Shadow Code."

Imagine you have a large, complex 3D sculpture (a mathematical curve called a superelliptic curve). You shine a light on it from a specific angle, and it casts a shadow on the wall.

The Sculpture: This is a complex mathematical function involving polynomials (equations with variables like $x$ ).
The Shadow: The authors take this complex 3D shape and project it onto a 2D wall. The "shadow" is a simple list of 0s and 1s (a binary code).
The Magic: The way they cast the shadow is special. They use a mathematical tool called a "multiplicative character" (think of it as a special filter or lens). This filter looks at the sculpture and decides: "Is this part of the shape a perfect square? If yes, write a 0. If no, write a 1."

Because the original sculpture is so complex and the "light" is cast in a very specific way, the resulting shadow (the code) has two amazing properties:

It's very long: It can carry a lot of data.
It's very distinct: Any two different shadows look very different from each other (high distance), even if the original sculptures were only slightly different.

2. Beating the Old Champions

For decades, the "champions" of these types of codes were called Delsarte–Goethals codes. They were great, but they had a limit: as you tried to make the messages longer, the amount of information you could send (the rate) dropped off very quickly, like a steep cliff.

The authors show that their new "Shadow Codes" are like a super-charged upgrade.

The Analogy: If the old codes were like a bicycle, the new codes are like a rocket ship.
The Result: For the same length of message and the same level of protection against noise, the new codes can carry exponentially more information than the old ones. In math terms, if the old code could carry 100 bits, the new one might carry millions or billions of bits for the same setup.

3. The "Stacking" Boost (Concatenation)

The authors also show how to make these codes even better by "stacking" them.

Imagine you have a strong, short code (the Shadow code).
You take a different, well-known code (Reed-Solomon, used in CDs and QR codes) and use it to organize many of these short Shadow codes together.
The Result: This creates a massive code that is still very efficient. The paper claims this stacked version is much better than trying to stack the old Delsarte–Goethals codes with Reed-Solomon codes. It's like building a skyscraper with a stronger foundation; you can go much higher without it falling over.

4. Why This Matters (Cryptography)

The paper mentions a specific application: Cryptography (making secret codes that are hard to break).

In modern cryptography, there is a concept called the "square" of a code. If you take two messages from your code and multiply them together in a specific way, you get a new set of messages.
For many codes, this "square" is small and predictable, which makes them vulnerable to attacks.
The authors prove that the "square" of their Shadow Code behaves like a random mess. It grows huge and unpredictable.
The Analogy: If a bad guy tries to attack your code by looking at the "shadows" of the shadows, they will find a chaotic, random-looking mess that is incredibly hard to crack. This makes these codes very attractive for creating secure digital signatures.

5. How to Read the Message (Decoding)

A code is useless if you can't read it back. The paper includes a recipe (an algorithm by Swastik Kopparty) to decode these messages.

The Problem: You receive a noisy shadow where some 0s turned into 1s and vice versa.
The Solution: The algorithm treats the problem like a puzzle. It tries to reconstruct the original "sculpture" (the polynomial) that created the shadow, even though the shadow is damaged. It uses a clever mathematical trick to filter out the noise and find the original shape.

Summary

The authors have built a new type of mathematical "shadow" that is:

Much larger than previous best codes (exponential improvement).
Very robust against noise.
Hard to crack for hackers because its mathematical structure looks random when squared.
Decodable using an efficient algorithm.

They achieved this by combining advanced number theory (polynomials over finite fields) with the geometry of curves, casting a "shadow" that turns complex math into a super-efficient communication tool.

Technical Summary: A New Class of Linear Codes

Problem Statement
The paper addresses the construction of linear codes over finite fields $\mathbb{F}_r$ with length $n$ and relative distance asymptotic to $1/2$ (specifically $d \approx n/2$ ). While binary codes with minimum distance roughly $n/2$ are fundamental, the Plotkin bound restricts the size of such codes to be extremely small when $d \ge n/2$ . In the regime where $d < n/2$ but $n - 2d = \Omega(\sqrt{n})$ , the best-known constructions have historically been non-linear Delsarte–Goethals codes. These codes, while effective, suffer from exponentially decaying rates as the length increases. The authors aim to construct linear codes that achieve comparable or better parameters, specifically targeting an exponential improvement in code size (rate) over Delsarte–Goethals codes while maintaining the relative distance regime of $1/2$ .

Methodology
The authors introduce a construction based on the theory of multiplicative character sums and superelliptic curves, termed Shadow Codes. The core strategy involves:

Field Setup: Utilizing an auxiliary field $\mathbb{F}_q$ (where $q$ is a prime power) to construct a code over a smaller base field $\mathbb{F}_r$ (where $r$ is a prime dividing $q-1$ ).
Superelliptic Curves: Selecting a collection of monic irreducible polynomials $P = \{p_1, \dots, p_L\}$ over $\mathbb{F}_q$ .
Character Mapping: Defining a map where codeword entries are determined by evaluating a multiplicative character $\chi_r$ of order $r$ on products of these polynomials. Specifically, for a message vector $(v_1, \dots, v_L) \in \mathbb{F}_r^L$ , the codeword at index $x \in \mathbb{F}_q$ is given by $\phi_r(\chi_r(\prod p_i(x)^{v_i}))$ , where $\phi_r$ is an isomorphism mapping the roots of unity to the additive group of $\mathbb{F}_r$ .
Geometric Interpretation: The "shadow" refers to the projection of the superelliptic curve $y^r = f(x)$ (where $f$ is the product of the polynomials) onto the x-axis. The zeroes of the codeword correspond to the x-coordinates where $f(x)$ is an $r$ -th power.
Concatenation: To improve parameters further, the authors propose concatenating these Shadow codes with Reed-Solomon (RS) codes.

Key Contributions and Results

Construction of Shadow Codes: The paper proves the existence of $\mathbb{F}_r$ -linear codes with length $n=q$ , dimension $k \approx q^{1/2-\epsilon}$ , and minimum distance $d \ge \frac{r-1}{r}q - O(q^{1-\epsilon})$ .
- Theorem I.1: Establishes the existence of these codes for any $\epsilon \in (0, 1/2)$ and sufficiently large $q$ .
- Corollary I.2: Specializes to binary codes ( $r=2$ ), yielding parameters $[q, \lfloor q^{1/2-\epsilon} \rfloor, d]$ with $d \ge q/2 - 2q^{1-\epsilon}$ .
Exponential Improvement over Delsarte–Goethals Codes:
- The authors demonstrate that for the regime $n - 2d = \Omega(\sqrt{n})$ , their linear Shadow codes have a size that is exponentially larger than Delsarte–Goethals codes.
- Proposition III.2: Shows that for a sequence of parameters, the ratio of the logarithm of the size of the Shadow code to the Delsarte–Goethals code is $\Omega(2^{m\delta/2}/m^2)$ , confirming an exponential gain. Unlike Delsarte–Goethals codes, the new codes are linear and possess a decoding algorithm.
Concatenation Boosts:
- RS-Shadow Concatenation (Theorem V.1): By concatenating a Reed-Solomon code with a Shadow code, the authors achieve a code of length $N = q^{n+1}$ with dimension $N^{1 - \frac{1}{2n+2} - \frac{2\epsilon}{n+1}}$ and relative distance asymptotic to $1/2$ .
- Comparison with RS-RM: The paper argues that replacing the inner Reed-Muller (RM) code in standard concatenations with a Shadow code yields a significantly higher rate for the same length and distance regime, as Shadow codes support larger dimensions than first-order RM codes.
Square of Shadow Codes and Cryptography:
- Theorem VI.1: Proves that the square of a Shadow code (under the Schur product) has dimension $L(L+1)/2$ provided $q$ is sufficiently large relative to the dimension $L$ . This mimics the behavior of random codes.
- Significance: Codes with high-dimensional squares are valuable for cryptographic applications (e.g., signature schemes) as they resist certain algebraic attacks. In contrast, the paper shows (Theorem VI.4) that the square of a concatenated RS-RM code has a dimension that is vanishingly small compared to the universal bound, making it less suitable for such applications.
Decoding Algorithm:
- Section VII: The paper presents an efficient decoding algorithm for binary Shadow codes based on Swastik Kopparty's method. This involves recovering a square-free message polynomial from noisy evaluations of the quadratic character, utilizing linear algebra and polynomial factorization.
Application to Number Theory:
- Section IV: The authors apply coding theoretic bounds (Plotkin and McEliece) to derive new results on exponential sums, specifically establishing lower bounds for the maximum value of certain character sums over finite fields.

Significance and Claims
The paper claims to provide a constructive proof of the existence of a new class of linear codes that outperform the long-standing Delsarte–Goethals non-linear codes in the regime of relative distance $1/2$ . The primary significance lies in the exponential improvement in code size (rate) while maintaining linearity and providing an explicit decoding algorithm. Furthermore, the paper highlights that the algebraic structure of these codes (specifically the behavior of their squares) makes them promising candidates for cryptographic applications, distinguishing them from other concatenated code families like RS-RM. The work also bridges coding theory and number theory by deriving new bounds on character sums.