Abstract
Linear codes with a few weights have important applications in authentication codes, secret sharing, consumer electronics, etc. The determination of the parameters such as Hamming weight distributions and complete weight enumerators of linear codes are important research topics. In this paper, we consider some classes of linear codes with a few weights and determine the complete weight enumerators from which the corresponding Hamming weight distributions are derived with help of some sums involving Legendre symbol.
Introduction
In coding theory, a linear code is traditionally characterized by its weight enumerator, which quantifies the number of codewords of a specific Hamming weight. However, advanced cryptographic applications—such as authentication codes and secret sharing schemes—often require a more granular description provided by the Complete Weight Enumerator (CWE). While a standard weight enumerator distinguishes only between zero and non-zero elements, the CWE tracks the exact frequency of every symbol in the alphabet $\mathbb{F}_p$.
Calculating the CWE is significantly more complex than determining the standard Hamming weight distribution. This research addresses this complexity by providing explicit formulas for the CWE of specific classes of linear codes over finite fields, particularly those with a "few" distinct weights (typically 3 to 5).
Methodology
The researchers utilize the Defining Set Method to construct these codes. A code is defined by selecting a specific subset $D$ of a large finite field $\mathbb{F}_q$ and applying a trace function to map elements back to a smaller field $\mathbb{F}_p$.
The technical framework relies on three primary pillars:
- Quadratic Defining Sets: The set $D$ is defined based on the condition $Tr(x^{p^\alpha+1}) = a$. This specific quadratic structure is the catalyst for generating codes with a limited number of weights.
- Exponential Sums: To count symbol occurrences, the authors employ Weil sums (specifically results from Coulter). These sums allow for the evaluation of how frequently the trace function yields specific values.
- Legendre Symbols: The derivations depend heavily on the Legendre symbol $\left(\frac{a}{p}\right)$, which indicates whether an integer is a quadratic residue modulo $p$. This tool is essential for partitioning codewords into cases based on the properties of the underlying finite field.
Key Insights and Results
A central finding of the paper is the role of structural sparsity. By carefully selecting the defining set, the authors demonstrate that it is possible to create codes where the vast majority of possible weights never occur. These "few-weight" codes are structurally "clean," a prerequisite for certain secret sharing protocols where access structures must be strictly defined.
The paper presents four main theorems (2.1 through 2.4) providing exact CWE and weight distributions. For instance, Theorem 2.1 identifies a class of 3-weight codes, as detailed in the following table:
Furthermore, the research explores more complex distributions, such as the 5-weight codes identified in Theorem 2.4. These codes provide a broader range of weights while maintaining the "minimal" property required for secure multi-party computation.
The authors also highlight that the parity of the ratio $m/d$ (where $e=2m$ is the field extension degree) is a critical factor. This parity determines the solvability of the underlying equations and, consequently, the resulting weight distribution.
Applications and Future Work
The derived codes meet the requirements for "minimal" linear codes, which are essential for designing efficient and secure multi-party computation and secret sharing schemes. By providing the exact multiplicity (how many codewords exist for each weight) and the exact exponents for the CWE polynomial, this work offers a complete "fingerprint" for these algebraic structures.
While the results are currently limited to the specific quadratic form $x^{p^\alpha+1}$ and even extension degrees, the techniques involving Legendre symbols offer a roadmap for future exploration. Extending these methods to more complex defining sets or odd extension degrees could lead to the discovery of additional classes of optimal few-weight codes.
Summary updated