Randomized Decoding of Linearized Reed-Solomon Codes Beyond the Unique Decoding Radius

Thomas Jerkovits, Hannes Bartz, Antonia Wachter-Zeh

Abstract

Linearized Reed–Solomon (LRS) codes are a versatile class of codes defined over the sum-rank metric, offering a generalization that bridges the gap between the Hamming and rank metrics. While their unique decoding properties are well-understood, their security in cryptographic applications depends on the difficulty of decoding beyond the unique decoding radius. This paper presents a novel randomized algorithm that exploits the specific block structure of LRS codes to outperform generic decoders. By transforming randomly guessed error supports into erasures and optimizing the process via linear programming, the authors provide a tighter assessment of the work factor required to break LRS-based cryptosystems.

Introduction

In the landscape of post-quantum cryptography, code-based systems are primary contenders for standardizing secure communication against quantum adversaries. Linearized Reed–Solomon (LRS) codes, which operate within the sum-rank metric, have emerged as particularly promising due to their flexibility. However, the security of these systems is fundamentally tied to the computational hardness of the decoding problem—specifically, the difficulty of recovering a codeword when the number of errors exceeds the unique decoding radius $t = \lfloor (d-1)/2 \rfloor$.

Historically, the security of LRS codes was evaluated using generic sum-rank decoders. These decoders treat all codes within the metric equally, failing to leverage the specific algebraic structure of LRS codes. This work addresses this gap by introducing a randomized decoding strategy tailored to the LRS framework, providing a more accurate measure of the "work factor" (computational effort) an attacker would face.

The Sum-Rank Metric and LRS Codes

The sum-rank metric is a hybrid measure that counts the rank of error blocks across multiple sub-spaces. It encompasses the Hamming metric (where blocks are of size 1) and the rank metric (where there is only one large block). LRS codes are Maximum Sum-Rank (MSR) codes, meaning they achieve the best possible trade-off between redundancy and error-correction capability within this metric. Their structure is defined by linearized polynomials, which allows for efficient unique decoding but presents a complex landscape for decoding beyond that limit.

Methodology: Randomized Support Guessing

The proposed algorithm shifts the decoding paradigm from pure error correction to a hybrid of error-erasure decoding. The core of the strategy involves four key steps:

  1. Support Guessing: The algorithm makes a randomized "guess" regarding the support of the error (the subspace where the error resides).
  2. Erasure Transformation: These guesses are treated as erasures. In coding theory, erasures are significantly easier to correct than errors because their locations are known; an erasure effectively costs only half as much as an unknown error in terms of the code's minimum distance.
  3. Error-Erasure Decoding: Using an efficient LRS error-erasure decoder, the algorithm attempts to recover the codeword. If the initial guess overlaps sufficiently with the actual error support, the decoder succeeds.
  4. Probabilistic Iteration: Since the initial guess may be incorrect, the process is repeated. The total complexity is determined by the probability of a "good" guess and the cost of each decoding attempt.

Optimization via Linear Programming

To minimize the expected work factor, the authors do not guess blindly. They employ a linear programming approach to determine the optimal probability distribution for guessing across different blocks of the LRS code. This optimization ensures that the algorithm focuses its computational resources on the most likely error configurations, significantly reducing the number of iterations required for success.

Evaluation and Results

The researchers validated their approach through a combination of rigorous mathematical proofs and numerical simulations. By testing the algorithm on field sizes such as $q=11$ and $q=2^4$, they demonstrated that the theoretical upper and lower bounds for the work factor are remarkably tight.

Key Findings

  • Superiority over Generic Decoders: The randomized LRS decoder consistently requires fewer operations than the best-known generic sum-rank decoders. By exploiting the block-wise structure of LRS codes, the algorithm finds "shortcuts" that generic methods miss.
  • Quantifiable Security Metrics: The study provides concrete formulas for calculating the work factor. In practical terms, the authors observed a significant drop in the $log_2$ of the work factor when moving from generic decoding to their optimized randomized approach.
  • Security Implications: While the algorithm is faster than previous methods, the complexity of decoding beyond the unique radius remains exponential. This confirms that LRS codes remain a robust foundation for cryptographic primitives, provided that parameters are chosen to account for these improved decoding efficiencies.

Conclusion

This work refines our understanding of the security margins of Linearized Reed–Solomon codes. By introducing a randomized decoder that treats guessed errors as erasures and optimizing the strategy through linear programming, the authors have established a new state-of-the-art for sum-rank decoding. Future research may extend this analysis to LRS codes with variable block sizes and further refine the computational costs associated with finding the optimal guessing distributions.

Summary updated

BibTeX
@inproceedings{jerkovits2023randomized,
  author = {Thomas Jerkovits and Hannes Bartz and Antonia Wachter-Zeh},
  title = {{Randomized Decoding of Linearized Reed-Solomon Codes Beyond the Unique Decoding Radius}},
  booktitle = {ISIT},
  year = {2023},
  doi = {10.1109/isit54713.2023.10206957},
}
Figure