Algebraic Cryptanalysis of the Rank Decoding and the MinRank problems
Rank-based cryptography is a promising field of code-based cryptography where one uses the rank metric instead of the traditional Hamming metric. The Rank Decoding (RD) and the MinRank (MR) problems are at the core of rank-based and multivariate-based cryptography.
In this talk, we present algebraic attacks against RD and MR, namely MaxMinors and SupportMinors. These attacks were introduced by Bardet et
al. (Eurocrypt and Asiacrypt 2020).
The MaxMinors attack has been devasting against ROLLO and RQC, two cryptosystems which made it to the Second Round of the NIST Post-Quantum Standardization Process; and the SupportMinors attack has been used by Beullens in his cryptanalysis of the Rainbow signature scheme, a 3rd Round Finalist in the aforementioned standardization process.
