On Software Implementation of Gabidulin Decoders

Johannes Kunz, Julian Renner, Georg Maringer, Thomas Schamberger, Antonia Wachter-Zeh

TL;DR

This paper demonstrates that theoretical complexity analysis—simply counting mathematical operations—is a poor predictor of real-world performance for cryptographic decoders. By implementing two major Gabidulin decoders (WBA and TDD) in C, the authors reveal that the Welch-Berlekamp Algorithm is roughly four times faster than the Transform Domain Decoder, directly contradicting theoretical models that favor the latter.

What Problem Does This Paper Address?

Gabidulin codes are a type of "maximum rank distance" (MRD) code, making them highly attractive for post-quantum cryptography (PQC). Specifically, they are a core component of the RQC (Rank Quasi-Cyclic) cryptosystem, a candidate in the NIST PQC standardization process.

In cryptography, speed is second only to security. To choose the best algorithms, researchers often rely on "complexity analysis," which counts how many additions or multiplications an algorithm performs. However, this paper addresses a critical gap: theoretical counts often ignore how these operations actually map to a computer's hardware (instruction sets). The authors set out to determine if the "theoretically superior" Transform Domain Decoder (TDD) actually holds up against the standard Welch-Berlekamp Algorithm (WBA) when running on modern x86-64 processors.

Methods

The authors implemented two primary decoding approaches in C:

  1. Welch-Berlekamp Algorithm (WBA): Currently used in RQC, this implementation utilizes a polynomial basis for finite field operations.
  2. Transform Domain Decoder (TDD): Theoretically more efficient for low-rate codes, this was implemented using a normal basis.

The "basis" refers to how elements of the finite field $\mathbb{F}_{q^m}$ are represented as bit-vectors.

  • Polynomial Basis: Operations like multiplication are handled via polynomial products and modular reduction (using techniques like the "comb method").
  • Normal Basis: Theoretically makes "q-power" operations (Frobenius automorphisms) "free" because they become simple cyclic bit-shifts.

The authors benchmarked these on a 2.3 GHz Intel Core i5, focusing on the specific parameters required for 128-bit security in RQC ($m=127, n=113, k=3$).

Datasets

The paper does not use external datasets. Instead, it evaluates the algorithms using:

  • Randomly generated Gabidulin codes.
  • Random messages and error words of maximum rank weight ($\tau_{max}$) to simulate worst-case decoding scenarios.
  • Micro-benchmarks of $10^6$ function calls for basic finite field operations (add, multiply, invert, etc.).

Key Insights and Ideas

  • The "Free" Shift Fallacy: In theoretical models, cyclic shifts in a normal basis are often treated as zero-cost. In reality, on an x86-64 architecture, a 127-bit cyclic shift requires multiple instructions (shifts, ORs, and bit-masking) to move data between 64-bit registers. These "negligible" costs dominate the runtime.
  • Hardware Synergy: Modern CPUs are exceptionally good at the bitwise XORs and shifts used in polynomial basis multiplication. Even though polynomial multiplication is "complex" on paper, it executes much faster than the "simpler" normal basis logic.
  • Basis Choice is Decisive: The performance gap isn't just about the algorithm's logic, but how the underlying math (the basis) interacts with the compiler and CPU. The polynomial basis multiplication was found to be 7.9 times faster than the normal basis version at the instruction level.

Key Results

  • Micro-benchmarks: Polynomial basis operations outperformed normal basis operations across the board. For example, an inversion took 0.53s (polynomial) vs. 2.9s (normal) per million calls.
  • Decoder Speed: For $10^3$ decoding operations:
  • WBA (Polynomial Basis): 1.75 seconds.
  • TDD (Normal Basis): 7.05 seconds.
  • The Verdict: Despite TDD requiring fewer generic multiplications in theory, the WBA is 4x faster in practice. This is largely because TDD relies heavily on q-power multiplications, which performed significantly worse than expected on actual hardware.

Limitations and Future Work

  • Non-Optimal Bases: For the specific extension degree used in RQC ($m=127$), an "optimal" normal basis does not exist. The authors had to use a "low-weight" normal basis instead. The results might shift slightly for values of $m$ where an optimal basis is available.
  • SIMD Optimization: The authors noted that they did not use x86 SSE/AVX (SIMD) instructions for their normal basis implementation. While RQC has an optimized SSE version for polynomial bases, a similar optimization for TDD might close some of the gap, though the authors suspect the polynomial basis would still lead.
  • Future Direction: The authors suggest that future research should focus on re-implementing these fields for different values of $m$ to see if TDD can ever reclaim its theoretical crown.

Summary updated

Abstract

This work compares the performance of software implementations of different Gabidulin decoders. The parameter sets used within the comparison stem from their applications in recently proposed cryptographic schemes. The complexity analysis of the decoders is recalled, counting the occurrence of each operation within the respective decoders. It is shown that knowing the number of operations may be misleading when comparing different algorithms as the run-time of the implementation depends on the instruction set of the device on which the algorithm is executed.
BibTeX
@inproceedings{kunz2020software,
  author = {Johannes Kunz and Julian Renner and Georg Maringer and Thomas Schamberger and Antonia Wachter-Zeh},
  title = {{On Software Implementation of Gabidulin Decoders}},
  booktitle = {ACCT},
  year = {2020},
  url = {https://openreview.net/forum?id=RV97eaScIF},
}

Loading related content...

Figure