List Decoding of 2-Interleaved Binary Alternant Codes

Chih-Chiang Huang, Hedongliang Liu, Lukas Holzbaur, Sven Puchinger, Antonia Wachter-Zeh

Abstract

This paper introduces a novel list decoding algorithm for 2-interleaved binary alternant codes, a class that includes widely used codes such as BCH and Goppa. By combining trivariate polynomial interpolation with subfield-specific multiplicity assignments, the authors demonstrate a decoding radius that can exceed the theoretical binary Johnson radius with high probability. The algorithm leverages the joint structure of interleaved codewords and the specific properties of binary subfields to improve error correction performance beyond traditional limits.

Introduction

In error correction, unique decoding is limited to correcting errors up to half the minimum distance of the code. List decoding offers a more powerful alternative by returning a list of all possible codewords within a larger radius, thereby increasing the likelihood of message recovery in high-noise environments. While list decoding for Reed-Solomon codes is well-established, applying these techniques to binary alternant codes—critical for applications like post-quantum cryptography—presents significant challenges. This work addresses these challenges by employing "interleaving," where multiple codewords share the same error locations, to push the decoding radius past the traditional Johnson radius.

Methods

The proposed decoding algorithm integrates three key concepts:

  1. Interleaving: Two codewords are treated as a single matrix where errors occur column-wise. This provides the decoder with more structural information to identify error locations.
  2. Trivariate Interpolation: Following the Parvaresh-Vardy approach, the algorithm finds a polynomial $G(X, Y, Z)$ that passes through points related to the received data. Using three variables instead of the usual two allows for a larger decoding radius.
  3. Subfield Multiplicities: Since the codes are binary but interpolation happens in an extension field, the authors use a technique from the Koetter-Vardy algorithm. They assign specific weights (multiplicities) to points based on their consistency with the binary subfield, treating the subfield constraint as "soft information" to guide the decoder.

The recovery process involves computing resultants of the interpolation polynomials to extract the original message polynomials $f(X)$ and $g(X)$.

Key Results

The algorithm was evaluated using synthetic simulations of 2-interleaved binary alternant codes with length $n=32$ and minimum distance $d=13$.

Comparison of decoding radii for various algorithms. The proposed method (Thm. 2) demonstrates a superior decoding radius ($t/n$) compared to Guruswami-Sudan and Koetter-Vardy benchmarks, successfully exceeding the Johnson bound.

As illustrated in Figure 1, the proposed algorithm's upper bound on the decoding radius is strictly higher than that of the Guruswami-Sudan, Koetter-Vardy, and standard Parvaresh algorithms for the chosen parameters. In simulations, the algorithm successfully decoded up to $t=10$ errors, whereas the standard binary Johnson radius for these parameters is approximately $7.5$.

Heatmap showing the success probability of the decoding algorithm for various multiplicity assignments $(m_1, m_2)$. The results indicate that specific combinations of multiplicities significantly enhance the probability of successful codeword recovery.

The success of the algorithm is probabilistic. Figure 2 shows how the choice of multiplicities $(m_1, m_2)$ affects the success rate. With optimal parameters, the failure probability becomes negligible. Furthermore, the authors prove that the list size remains polynomial relative to the code parameters, ensuring computational feasibility despite the increased complexity of trivariate interpolation.

Conclusion

This work demonstrates that leveraging subfield properties and interleaving can significantly enhance the list decoding capabilities for binary alternant codes. While the interpolation step is computationally intensive ($O(n^2 m_1^8)$) and the success is probabilistic, the ability to exceed the Johnson bound represents a significant advancement. Future research may explore more efficient interpolation architectures and the extension of this framework to $L$-interleaved codes for even greater decoding radii.

Summary updated

Abstract

This paper is concerned with list decoding of 2-interleaved binary alternant codes. The principle of the proposed algorithm is based on a combination of a list decoding algorithm for (interleaved) Reed-Solomon codes and an algorithm for (non-interleaved) alternant codes. A new upper bound on the decoding radius is derived and the list size is shown to scale polynomially in the code parameters. While it remains an open problem whether this upper bound is achievable, the provided simulation results show that a decoding radius exceeding the binary Johnson radius can be achieved with a high probability of decoding success by the proposed algorithm.
BibTeX
@inproceedings{huang2022list,
  author = {Chih-Chiang Huang and Hedongliang Liu and Lukas Holzbaur and Sven Puchinger and Antonia Wachter-Zeh},
  title = {{List Decoding of 2-Interleaved Binary Alternant Codes}},
  booktitle = {ISIT},
  year = {2022},
  url = {https://openreview.net/forum?id=1xJMm1lP0b},
}
Figure