Preventing Timing Attacks Against RQC Using Constant Time Decoding of Gabidulin Codes

摘要

This paper studies the resistance of the code-based encryption scheme RQC to timing attacks. We describe two chosen ciphertext timing attacks that rely on a correlation between the weight of the error to be decoded and the running time of Gabidulin code's decoding algorithm. These attacks are of theoretical interest as they outperform the best known algorithm to solve the rank syndrome decoding problem in term of complexity. Nevertheless, they are quite impracticable in real situations as they require a huge number of requests to a timing oracle. We also provide a constant-time algorithm for the decoding of Gabidulin codes that prevent these attacks without any performance cost for honest users.