Efficient Decoding of Gabidulin Codes for the RQC NIST Proposal

The RQC cryptosystem is a candidate in the NIST-PQC competition standardizing post- quantum secure algorithms. Beside the cryptographic security the performance of the algorithm is of great importance, in which the decryption of Gabidulin codes takes a major part. In this work, we compare the performance of different Gabidulin decoders that are implemented in software. The theoretical complexity analysis of the decoders is recalled counting the occurrence of each operation within the respective decoders. We show 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. As the decoders are used for cryptographic purposes, we review and derive modifications such that their execution time does not depend on the inputs.