The Blockwise Rank Syndrome Learning Problem and Its Applications to Cryptography

A notion of blockwise errors in the context of rank-based cryptography has recently been introduced in [28]. It allowed to choose more interesting parameters for the original LRPC and RQC schemes, which contributed to greatly improve their performances. Prior to that, it had been proposed in [3, 16] to consider several decoding instances which are correlated (this is called the multi-syndromes approach). The goal was similar and these works also lead to new schemes with very competitive public key and ciphertext sizes. In this paper, we show that these two approaches can be combined to construct even more efficient generalized RQC and LRPC schemes. We introduce the \(\ell \) - \(\textsf{RSL}\) problem, which is a version of the Rank Support Learning problem relevant to the multi-syndrome approach but where the errors have a blockwise structure. Our generalizations rely on its difficulty. Concretely, we can obtain very interesting sizes. For 128-bit security, we propose parameters for which the sum of the public key and the ciphertext is only 1.4 kB for our generalized RQC and 1.7 kB for our generalized LRPC scheme. This is a \(40\%\) gain compared to [16, 28], our RQC doing even better than KYBER which features 1.5 kB. Besides these new schemes, we provide new attacks on the \(\ell \) - \(\textsf{RD}\) problem introduced in [28]. In particular, they allow us to cryptanalyze all blockwise LRPC parameters proposed in [28] (with an improvement of more than 40 bits for structural attacks). We also describe combinatorial and algebraic attacks for the \(\ell \) - \(\textsf{RSL}\) problem we introduce.