RQC Revisited and More Cryptanalysis for Rank-Based Cryptography

In this paper, we revisit the Rank Quasi-Cyclic (RQC) (Melchor et al., IEEE IT, 2018) encryption scheme by proposing three possible variations for its design. Our first improvement relies on the introduction of Augmented Gabidulin codes, a new family of decodable codes exploiting the concept of support erasure for the rank metric. Following the work of Melchor et al. (PQCrypto, 2022), our second improvement uses multiple syndromes to increase the weight of the error to be decoded. As pioneered in Melchor et al. (NIST PQC, 2020), our third variation considers non-homogeneous error weights in order to decrease the parameters. These improvements can be combined together to design schemes offering various trade-offs in term of security and size. Our Multi-UR-AG (multiple syndromes, unstructured, augmented Gabidulin) scheme achieves a size of 11kB (public key + ciphertext) for 128 bits of security while featuring a conservative design as it relies on pure random instances without any ideal structure. Besides, our NH- Multi-RQC-AG (non-homogeneous error, multiple syndromes, ideal structure, augmented Gabidulin) achieves a size of 2.7 kB for 128 bits of security, namely a 50 % improvement with respect to classical RQC. Our second and third variations respectively rely on the security of the <inline-formula> <tex-math notation="LaTeX">$\textsf {RSL} $ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$\textsf {NHRSD} $ </tex-math></inline-formula> problems (or <inline-formula> <tex-math notation="LaTeX">$\textsf {NHRSL} $ </tex-math></inline-formula> when considered together). In this paper, we also provide new security analysis and attacks for these problems. While these results are important for our new schemes, they are of independent interest as well. Our security analysis for the <inline-formula> <tex-math notation="LaTeX">$\textsf {RSL} $ </tex-math></inline-formula> problem provides an improvement on the recent algebraic attacks for some instances. In addition, we show that the <inline-formula> <tex-math notation="LaTeX">$\textsf {RSL} $ </tex-math></inline-formula> problem can be solved in polynomial time when <inline-formula> <tex-math notation="LaTeX">$N \geq (k+1) r\frac {m}{m-r}$ </tex-math></inline-formula>, this improves the best known combinatorial attack (Gaborit et al., Crypto, 2017). We also propose the first combinatorial attack against the <inline-formula> <tex-math notation="LaTeX">$\textsf {NHRSD} $ </tex-math></inline-formula> problem along with a precise complexity analysis of the algebraic attack described Melchor et al. (NIST PQC, 2020). At last, we combine these analysis to provide an attack against the <inline-formula> <tex-math notation="LaTeX">$\textsf {NHRSL} $ </tex-math></inline-formula> problem.