Title: Algebraic Cryptanalysis against the Rank Decoding
and the MinRank problems
Abstract: 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.
Keywords: Post-Quantum Cryptography, Error Correcting Codes, Algebraic Cryptanalysis, Gröbner Basis
