Efficient Decoding of Twisted GRS Codes and Roth-Lempel Codes

Technical Summary: Efficient Decoding of Twisted GRS Codes and Roth–Lempel Codes

Problem Statement
Maximum Distance Separable (MDS) codes are fundamental to reliable communication, distributed storage, and secret sharing. While Generalized Reed–Solomon (GRS) codes constitute the majority of known MDS codes and benefit from well-understood algebraic structures and efficient decoding algorithms, they possess strong algebraic structures that can be detrimental in code-based cryptography (e.g., susceptible to the Sidelnikov–Shestakov and Wieschebrink attacks). Consequently, non-GRS MDS codes are of significant theoretical and practical interest. Two prominent families of such codes are Twisted Generalized Reed–Solomon (TGRS) codes and Roth–Lempel codes.

Despite extensive research into the construction and structural properties of these non-GRS codes, their decoding algorithms have lagged behind. Existing decoding methods for TGRS codes are largely restricted to single-twist cases with quadratic time complexity ($O(n^2)$), and no efficient decoding algorithms have been reported for Roth–Lempel codes. Furthermore, current approaches are limited to unique decoding within the classical radius of $\lfloor(n-k)/2\rfloor$, leaving the potential for list decoding beyond this radius largely unexplored for these families.

Methodology
The authors propose a unified framework for decoding TGRS and Roth–Lempel codes based on the Guruswami–Sudan (GS) list decoding algorithm. The core strategy involves leveraging the structural relationship between these non-GRS codes and standard GRS codes:

1. Twisted GRS (TGRS) Codes: The authors observe that any TGRS code with pseudo-dimension $k'$ is a subcode of a GRS code of length $n$ and dimension $k'$. They propose a two-stage decoding process:

   • List Generation: Apply the near-linear time Guruswami–Sudan algorithm to the containing GRS code $C_{GRS}(\alpha, v, k')$ to generate a list of candidate polynomials.
   • Filtering: Filter this list by checking if the candidate polynomials satisfy the specific "twist" constraints (i.e., whether they belong to the twisted polynomial space $P_{TGRS}(k, T)$). This filtering step is efficient, requiring only coefficient comparisons.

2. Roth–Lempel Codes: The authors utilize the observation that puncturing a Roth–Lempel code at its last coordinate yields a standard GRS code. The decoding procedure involves:

   • Puncturing: Remove the last coordinate of the received word.
   • List Generation: Apply the Guruswami–Sudan algorithm to the punctured GRS code.
   • Re-encoding and Verification: Re-encode each candidate polynomial into a full Roth–Lempel codeword and retain only those candidates whose Hamming distance to the original received word is within the decoding radius.

3. AMD-Assisted Decoding: To resolve ambiguity when the list size exceeds one (i.e., beyond the unique-decoding radius), the authors integrate Algebraic Manipulation Detection (AMD) codes. Messages are pre-encoded with a systematic AMD tag before TGRS or Roth–Lempel encoding. During decoding, candidates in the output list are verified against the AMD tag, allowing the correct message to be identified with high probability.

Key Contributions and Results

• Near-Linear Time Decoding: The paper presents the first explicit decoding algorithms for Roth–Lempel codes and significantly improves upon existing TGRS decoders. Under suitable parameter conditions (specifically for fixed-rate codes), both list and unique decoding algorithms achieve a running time of $O(n \log^2 n \log \log n)$, improving upon the previously best-known $O(n^2)$ complexity.
• Extended Twist Capacity for TGRS: The proposed TGRS decoder supports a number of twists $\ell$ up to $O(n \log^2 n \log \log n)$ (and up to $O(n^2)$ for fixed-rate codes under specific constraints), a substantial improvement over prior work which was restricted to the single-twist case ($\ell=1$).
• Beyond Unique-Decoding Radius: The algorithms function as list decoders capable of correcting errors beyond the classical unique-decoding radius of $\lfloor(n-k)/2\rfloor$.
  • For TGRS codes, the list decoding radius is $\tau < n - \sqrt{n(k'-1)}$, where $k'$ is the pseudo-dimension.
  • For Roth–Lempel codes, the radius is $\tau < (n-1) - \sqrt{(n-1)(k-1)}$.
• Unique Decoding Conditions: The authors derive conditions under which the list decoder yields a unique solution, thereby providing efficient unique decoders for MDS TGRS and Roth–Lempel codes. For TGRS, unique decoding is guaranteed when $k' < \frac{(n+k)^2}{4n} + 1$.
• AMD Integration: The paper provides an explicit trade-off between redundancy and error probability for the AMD-assisted framework. By adding a small number of redundancy symbols (e.g., four symbols), the probability of failing to identify the unique transmitted message from the list can be reduced to $O(1/q)$.

Significance
The paper claims to address critical gaps in the decoding theory of non-GRS MDS codes. By demonstrating that TGRS and Roth–Lempel codes can be decoded with near-linear complexity, the work removes a major barrier to their practical deployment. The ability to handle a super-constant number of twists in TGRS codes is particularly significant for cryptographic applications, as recent cryptanalytic results suggest that schemes using only a constant number of twists are vulnerable. Furthermore, providing the first efficient decoders for Roth–Lempel codes opens the door to utilizing this family of codes in scenarios requiring high error correction or specific structural properties distinct from GRS codes. The integration of AMD codes offers a practical mechanism to recover unique messages from list outputs, bridging the gap between theoretical list decoding capabilities and practical unique decoding requirements.