On Software Implementation of Gabidulin Decoders

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

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.

Introduction

Gabidulin codes are a class of maximum rank distance (MRD) codes that have gained significant attention in the field of post-quantum cryptography (PQC). They serve as a foundational element in the RQC (Rank Quasi-Cyclic) cryptosystem, which is currently a candidate in the NIST PQC standardization process. In cryptographic applications, the efficiency of decoding algorithms is paramount. Traditionally, researchers have relied on theoretical complexity analysis—counting the number of field additions and multiplications—to evaluate and compare algorithms. However, this paper demonstrates that such metrics can be poor predictors of actual software performance on modern hardware.

Methodology

The study focuses on two primary decoding algorithms for Gabidulin codes:

  1. Welch-Berlekamp Algorithm (WBA): The standard decoder currently employed in RQC, implemented using a polynomial basis for finite field $\mathbb{F}_{q^m}$ operations.
  2. Transform Domain Decoder (TDD): A decoder theoretically optimized for low-rate codes, implemented using a normal basis.

The choice of basis significantly impacts operation efficiency. In a polynomial basis, multiplication involves polynomial products and modular reduction. In a normal basis, the Frobenius automorphism ($q$-power operation) is theoretically "free" as it corresponds to a simple cyclic bit-shift. The authors implemented these decoders in C and benchmarked them on a 2.3 GHz Intel Core i5 processor using parameters for 128-bit security ($m=127, n=113, k=3$).

Complexity Analysis vs. Real-world Performance

Theoretical models often favor the TDD due to its lower count of generic multiplications. However, these models frequently overlook the actual cost of operations on specific architectures like x86-64. For instance, while a cyclic shift is theoretically a single operation, implementing a 127-bit shift on 64-bit registers requires multiple instructions (shifts, ORs, and masking), negating the "zero-cost" assumption.

Operation counts for WBA and TDD decoders for $m=127, n=113, k=3$

As shown in the operation counts above, the TDD avoids standard multiplications but introduces a high volume of other operations like "multiply by $\alpha^{[i]}$" and "q-power". The performance of these operations depends heavily on the underlying basis.

Results

Micro-benchmarks revealed that polynomial basis operations consistently outperformed their normal basis counterparts on the target hardware.

Micro-benchmarks of finite field operations (time in seconds for $10^6$ calls)

The data indicates that polynomial basis multiplication is approximately 7.9 times faster than normal basis multiplication. Furthermore, inversion in the polynomial basis (0.53s) is significantly faster than in the normal basis (2.9s).

When evaluating the full decoders, the results were stark. For 1,000 decoding operations, the WBA (Polynomial Basis) took 1.75 seconds, while the TDD (Normal Basis) took 7.05 seconds. Despite the theoretical advantages of the TDD, the WBA proved to be 4 times faster in practice. This discrepancy arises because modern CPUs are highly optimized for the bitwise XORs and shifts required for polynomial basis arithmetic, whereas the normal basis logic does not map as efficiently to the instruction set.

Conclusion

This research highlights the critical importance of hardware-aware implementation in algorithm selection for cryptography. Theoretical operation counts can be misleading if they do not account for the varying costs of those operations on actual processors. For the parameters used in RQC, the Welch-Berlekamp Algorithm remains the superior choice for software implementation due to its synergy with polynomial basis arithmetic on standard CPU architectures.

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},
}
Figure