Randomized Decoding of Gabidulin Codes Beyond the Unique Decoding Radius

Julian Renner, Thomas Jerkovits, Hannes Bartz, Sven Puchinger, Pierre Loidreau, Antonia Wachter-Zeh

Introduction

In the landscape of post-quantum cryptography, rank-metric coding theory has emerged as a robust foundation for secure communication. Among these, Gabidulin codes—the rank-metric counterparts to Reed-Solomon codes—play a pivotal role. Traditionally, decoding these codes is straightforward up to the unique decoding radius (half the minimum distance). However, decoding beyond this threshold, known as the Search-Gab problem, is computationally intensive and serves as the security basis for several cryptosystems.

This paper introduces a novel randomized algorithm designed to decode Gabidulin codes beyond the unique decoding radius. By leveraging a "guess-and-verify" strategy focused on error subspaces, the authors achieve an exponential speedup over existing generic decoders, necessitating a significant re-evaluation of current cryptographic security margins.

The Search-Gab Problem

The security of rank-metric cryptosystems like RAMESSES and Faure–Loidreau relies on the hardness of finding a codeword given a received word corrupted by a high-rank error. While unique decoding is efficient, the complexity of decoding increases dramatically as the error rank $w$ exceeds the unique decoding radius $t = \lfloor (d-1)/2 \rfloor$. Prior to this research, attackers were limited to generic Rank Support Recovery (RSD) decoders, which do not exploit the specific algebraic structure of Gabidulin codes.

Methodology: Column-Erasure-Aided Randomized Decoding

The authors propose a Column-Erasure-Aided Randomized Decoder. The algorithm's efficiency stems from the realization that one does not need to identify the entire error space to succeed. Instead, identifying a sufficient subspace of the error allows the problem to be reduced to a solvable state.

The decoding process follows these steps:

  1. Subspace Guessing: The algorithm selects a random $\delta$-dimensional subspace.
  2. Erasure Transformation: This guessed subspace is treated as part of the error's row space (effectively treating them as "erasures").
  3. Rank Reduction: By accounting for these erasures, the effective rank of the remaining unknown error is reduced.
  4. Polynomial-Time Decoding: If the intersection between the guessed subspace and the actual error space is large enough, the remaining error falls within the capability of standard, fast error-erasure decoders.
  5. Iteration: If a valid codeword is not found, the process repeats with a new random guess.

The complexity of this approach is governed by the probability of a "good" guess, which the authors quantify using Gaussian binomial coefficients.

Impact on Cryptographic Security

The primary contribution of this work is the demonstration that Gabidulin codes are more vulnerable to decoding attacks than previously assumed. The authors evaluated their algorithm against parameter sets proposed for the RAMESSES and modified Faure–Loidreau (FL) systems.

Parameter Set ($q, m, n, k, w$) New Randomized Decoder ($W_{RD}$) Combinatorial RSD ($W_{Comb}/N$) Algebraic RSD ($W_{Alg}$)
RAMESSES (2, 64, 64, 32, 19) $2^{257.20}$ $2^{571.21}$ $2^{460.01}$
Modified FL (2, 82, 82, 48, 20) $2^{290.92}$ $2^{838.54}$ $2^{504.70}$

As shown in the table, the results indicate a massive reduction in the work factor. For instance, the security of the RAMESSES system drops from $2^{460}$ to $2^{257}$. While still computationally high, this exponential reduction significantly narrows the security margin and forces a recalibration of safe parameters for rank-metric primitives.

Insights and Limitations

A key insight of the paper is that for Gabidulin codes, where the extension degree $m$ is typically greater than or equal to the length $n$, guessing the row space is more efficient than guessing the column space. This exploitation of the code's specific structure is what allows the randomized decoder to outperform generic combinatorial or algebraic attacks.

However, the algorithm has limitations. It cannot be directly applied to the RQC (Rank Quasi-Cyclic) cryptosystem. RQC errors possess a specific structure where a general search might identify a "close" codeword that is not the unique codeword required for decryption. Additionally, the theoretical bounds for the work factor are less tight for very small parameters due to approximations in the Gaussian binomial formulas.

Conclusion and Future Work

The introduction of the Column-Erasure-Aided Randomized Decoder represents a major shift in how the security of Gabidulin-based systems is assessed. By moving beyond generic decoders, the authors have provided a more accurate benchmark for the hardness of the Search-Gab problem. Future research may focus on integrating list decoding techniques into this randomized framework to further enhance the success probability of each iteration, potentially leading to even more efficient decoding strategies.

Summary updated

Abstract

We address the problem of decoding Gabidulin codes beyond their unique error-correction radius. The complexity of this problem is of importance to assess the security of some rank-metric code-based cryptosystems. We propose an approach that introduces row or column erasures to decrease the rank of the error in order to use any proper polynomial-time Gabidulin code error-erasure decoding algorithm. The expected work factor of this new randomized decoding approach is a polynomial term times $$q^{m(n-k)-w(n+m)+w^2+\min \{2\xi (\frac{n+k}{2}-\xi ),wk\} }$$, where n is the code length, q the size of the base field, m the extension degree of the field, k the code dimension, w the number of errors, and $$\xi := w-\tfrac{n-k}{2}$$. It improves upon generic rank-metric decoders by an exponential factor.
BibTeX
@inproceedings{renner2020randomized,
  author = {Julian Renner and Thomas Jerkovits and Hannes Bartz and Sven Puchinger and Pierre Loidreau and Antonia Wachter-Zeh},
  title = {{Randomized Decoding of Gabidulin Codes Beyond the Unique Decoding Radius}},
  booktitle = {PQCrypto},
  year = {2020},
  doi = {10.1007/978-3-030-44223-1\_1},
}
Figure