RQC revisited and more cryptanalysis for Rank-based Cryptography

We propose two main contributions: first, we revisit the encryption scheme Rank Quasi-Cyclic (RQC) [1] by introducing new efficient variations, in particular, a new class of rank metric codes, namely the Augmented Gabidulin codes; second, we propose new attacks against the Rank Support Learning (RSL), the Non-Homogeneous Rank Decoding (NHRD), and the Non-Homogeneous Rank Support Learning (NHRSL) problems.
RSL is primordial for all recent rank-based cryptosystems such as Durandal [2] or LRPC with multiple syndromes [3], moreover, NHRD and NHRSL, together with RSL, are at the core of our new schemes.
The new attacks we propose are of both types: combinatorial and algebraic. For all these attacks, we provide a precise analysis of their complexity.

Overall, when all of these new improvements for the RQC scheme are put together, and their security evaluated with our different attacks, they enable one to gain 50% in parameter sizes compared to the previous RQC version.
More precisely, we give very competitive parameters, around 11 KBytes, for RQC schemes with unstructured public key matrices. This is currently the only scheme with such short parameters whose security relies solely on pure random instances without any masking assumptions, contrary to McEliece-like schemes. At last, when considering the case of Non-Homogeneous errors, our scheme permits to reach even smaller parameters.

Keywords: Rank Metric, Encryption, Code-Based Cryptography, Gabidulin Codes.

[1] : RQC submission for NIST PQC Standardization Process 2nd Round (https://pqc-rqc.org/doc/rqc-specification_2020-04-21.pdf)
[2] : "Durandal: a rank metric based signature scheme", Eurocrypt 2019, Aragon, Blazy, Gaborit, Hauteville, Zémor
[3] : "LRPC codes with multiple syndromes: near ideal-size KEMs without ideals", PQCrypto 2022, Aguilar-Melchor, Aragon, Dyseryn, Gaborit, Zémor.