Support-Guessing Decoding Algorithms in the Sum-Rank Metric

Thomas Jerkovits, Hannes Bartz, Antonia Wachter-ZeharXiv 2024 · DOI · arXiv

Introduction

The sum-rank metric has emerged as a critical mathematical framework for next-generation, quantum-resistant cryptography. By partitioning vectors into blocks and measuring weight as the sum of the ranks of these blocks, it offers a versatile middle ground between the traditional Hamming metric and the rank metric. This research provides a comprehensive update to the decoding complexity of codes in this metric, deriving tighter average-case bounds and introducing optimized algorithms that significantly outperform previous generic methods.

The Syndrome Decoding Problem in the Sum-Rank Metric

In code-based cryptography, security often hinges on the hardness of the Syndrome Decoding Problem (SDP). While SDP is well-characterized in Hamming and rank metrics, the sum-rank metric is a more recent development. It is particularly attractive because it allows for smaller cryptographic keys than Hamming-based systems while avoiding certain structural vulnerabilities inherent in pure rank-metric codes.

However, establishing secure parameters requires precise estimates of decoding complexity. Previous research focused largely on worst-case scenarios, leading to relatively loose complexity bounds. This work addresses the gap by analyzing average-case complexity for both unique and "beyond unique" decoding, providing a more realistic assessment of the security margins provided by sum-rank codes.

Methodology: Support-Guessing and Optimization

The authors focus on support-guessing algorithms. In these strategies, a decoder attempts to identify the subspace (the support) containing the error. Once the support is correctly identified, the error can be resolved via standard linear algebra. To optimize this process, the authors employ several key techniques:

  • Linear Programming (LP) Optimization: They use LP to determine the mathematically optimal distribution for guessing supports, thereby minimizing the expected decoding time.
  • Independent Block Heuristic: For large-scale parameters where solving the LP becomes computationally prohibitive, the authors introduce a heuristic that treats blocks as independent. They demonstrate that this heuristic is highly accurate in the asymptotic regime, where the number of blocks tends toward infinity.
  • Prange-like Adaptation: The classic Prange algorithm from Hamming-metric decoding is adapted to the sum-rank metric to handle scenarios with very large error weights.

Randomized Decoding for Linearized Reed-Solomon (LRS) Codes

A major contribution of the paper is a new randomized decoding algorithm specifically designed for Linearized Reed-Solomon (LRS) codes. Unlike generic decoders that require a perfect guess of the error support, this algorithm utilizes an "error-and-erasure" approach.

This decoder succeeds as long as there is sufficient overlap between the guessed support and the actual error support. By trading unknown errors for known erasures, the algorithm leverages efficient algebraic decoders to fill in missing information. This approach results in a massive reduction in complexity; for certain parameters (e.g., $n=48, k=24$), the log-complexity was shown to drop from approximately 800 to 200 compared to generic methods.

Key Results and Asymptotic Insights

The research yields significantly tighter upper bounds for generic decoding, particularly for codes with many small blocks—a scenario where previous bounds were notably loose. The authors also demonstrate that as the number of blocks increases, the distribution of error weights converges to a Boltzmann distribution. This allows for clean, precise complexity estimates in the limit, providing a roadmap for cryptographers to map "easy," "hard," and "no solution" regions for sum-rank decoding.

Limitations and Future Work

While this work advances the state-of-the-art, several avenues remain for future exploration:

  • List Decoding: The current analysis of decoding beyond the unique radius assumes a "genie-aided" decoder to select the correct solution from a list. Determining the maximum list size for LRS codes remains an open problem.
  • Advanced ISD Techniques: The authors suggest that adapting more advanced Information Set Decoding (ISD) techniques, such as ball-collision or Stern’s algorithm, could further reduce complexity in the sum-rank metric.
  • Structural Vulnerabilities: While this paper addresses generic decoding (attacks applicable to any code), future research must continue to investigate whether the specific algebraic structure of LRS codes permits specialized shortcuts for attackers.

Summary updated

Abstract

The sum-rank metric generalizes the Hamming and rank metric by partitioning vectors into blocks and defining the total weight as the sum of the rank weights of these blocks, based on their matrix representation. In this work, we explore support-guessing algorithms for decoding sum-rank-metric codes. Support-guessing involves randomly selecting candidate supports and attempting to decode the error under the assumption that it is confined to these supports. While previous works have focused on worst-case scenarios, we analyze the average case and derive an optimal support-guessing distribution in the asymptotic regime. We show that this distribution also performs well for finite code lengths. Our analysis provides exact complexity estimates for unique decoding scenarios and establishes tighter bounds beyond the unique decoding radius. Additionally, we introduce a randomized decoding algorithm for Linearized Reed--Solomon (LRS) codes. This algorithm extends decoding capabilities beyond the unique decoding radius by leveraging an efficient error-and-erasure decoder. Instead of requiring the entire error support to be confined to the guessed support, the algorithm succeeds as long as there is sufficient overlap between the guessed support and the actual error support. As a result, the proposed method improves the success probability and reduces computational complexity compared to generic decoding algorithms. Our contributions offer more accurate complexity estimates than previous works, which are essential for understanding the computational challenges involved in decoding sum-rank-metric codes. This improved complexity analysis, along with optimized support-guessing distributions, provides valuable insights for the design and evaluation of code-based cryptosystems using the sum-rank metric. This is particularly important in the context of quantum-resistant cryptography.
BibTeX
@misc{jerkovits2024support,
  author = {Thomas Jerkovits and Hannes Bartz and Antonia Wachter-Zeh},
  title = {{Support-Guessing Decoding Algorithms in the Sum-Rank Metric}},
  year = {2024},
  eprint = {2410.15806},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.15806},
}
Figure