Séminaire

Date : 8 novembre 2022 14:00 - Salle :Amphi Bruno Garcia Algebraic Cryptanalysis and Contributions to Post-Quantum Cryptography based on Error-Correcting Codes in the Rank-metric Maxime BROS, Doctorant - Laboratoire XLIM Limoges

Rank-based cryptography is a subfield of code-based cryptography where one uses the rank metric instead of the traditional Hamming metric. The Rank Decoding (RD) and the MinRank problems are at the core, respectively, of rank-based cryptography and multivariate-based cryptography. Moreover, RD reduces to MinRank, thus the MinRank problem is important in rank-based cryptography as well.

In this thesis, we introduced two algebraic attacks against RD and MinRank, namely the MaxMinors and the SupportMinors attacks. These attacks led to two publications [1,2] and caused ROLLO and RQC not to move to the 3rd Round of the NIST Post-Quantum Standardization process. Note also that the SupportMinors attack has been used by Beullens in the cryptanalysis of the Rainbow signature scheme [3], 3rd Round Finalist in this standardization process.

We also improved the Rank Quasi-Cyclic (RQC) encryption scheme [7], and proposed two new schemes with competitive parameters. One of these scheme does not rely on the ideal structure, thus its security relies solely on decoding random codes when given several syndromes, i.e. RSL problem. To study the complexity of these new schemes, we propose new attacks against some important variants of the RD problem, namely Non-Homogeneous RSD and RSL (NHRSD and NHRSL) and Rank Support Learning (RSL).

We will also present the cryptanalysis of the rank-based signature scheme RPS [4] that we published in [5], and a reduction that yields new attacks against the PSSI problem which is at the core of the Durandal signature scheme [6].

Last but not least, in this thesis, we introduced a new problem, namely the SquareSpace problem. We will present this problem, study its complexity and propose a signature scheme based on it, together with its implementation in C.

[1]: "An algebraic attack on rank metric code-based cryptosystems", Eurocrypt 2020, by Bardet, Briaud, Bros, Gaborit, Neiger, Ruatta, Tillich.

[2]: "Improvements of algebraic attacks for solving the rank decoding and min- rank problems", Asiacrypt 2020, by Bardet, Bros, Cabarcas, Gaborit, Perlner, Smith-Tone, Tillich, Verbel.

[3]: "Breaking rainbow takes a weekend on a laptop", Crypto 2022, by Beullens.

[4]: "Rank preserving code-based signature", ISIT 2020, by Lau, Tan.

[5]: "Cryptanalysis of the rank preserving signature", IMACC 2021, by Aragon, Bros, Gaborit.

[6]: "Durandal: a rank metric based signature scheme", Eurocrypt 2019, by Aragon, Blazy, Gaborit, Hauteville, Zémor.

[7]: RQC, 2nd Round Submission for NIST PQC Standardization Process by Aguilar Melchor, Aragon, Bettaieb, Bidoux, Blazy, Bros, Couvreur, Deneuville, Gaborit, Zémor, Hauteville.