Anthony Fraga. RAID - Compact PKE bridging RQC and LRPC cryptosystem paradigm

mardi 30 juin 2026, 14:00 → 15:00 Europe/Paris

Abstract: We introduce Rank Additive Ideal Decoding (RAID), a new rank-based encryption framework that bridges the design of the RQC and LRPC cryptosystems. In contrast to RQC, whose ciphertext has two components, RAID produces a single-component ciphertext by adding an LRPC error directly to an encoded message. The decryption procedure requires to multiply the ciphertext by the secret key and leverages an encoding of the message compatible with this multiplication. The security of the scheme relies on the hardness of the Blockwise Ideal Rank Support Learning (BIRSL) problem and on the Blockwise Ideal indistinguishability of LRPC (BILRPC) codes. Under these assumptions, we prove INDCPA security for the PKE and obtain an INDCCA KEM via the Fujisaki-Okamoto transform.

To instantiate this framework, we introduce Gabidulin-LowRank codes, a new family of codes defined as a direct sum of an augmented Gabidulin code and a code with low rank weight rows in its generator matrix. These codes are specifically designed to be compatible with the multiplication by the secret key. We identify and bound three sources of decoding failure, which we use to derive concrete parameters.

Our KEM achieves a sum of public key and ciphertext sizes that outperform ML-KEM at all three NIST security levels, first times happening for a code-based KEM to the best of our knowledge. In addition, it significantly improves existing rank-based schemes, including the most recent optimized variants of RQC and LRPC schemes.