International Association
for Cryptologic Research

DME is a multivariate scheme submitted to the call for additional signatures recently launched by NIST. Its performance is one of the best among all the candidates. The public key is constructed from the alternation of very structured linear and non-linear components that constitute the private key, the latter being defined over an extension field. We exploit these structures by proposing an algebraic attack which is practical on all DME parameters.

The Support-Minors (SM) method has opened new routes to attack multivariate schemes with rank properties that were previously impossible to exploit, as shown by the recent attacks of [1] and [2] on the Round 3 NIST candidates GeMSS and Rainbow respectively. In this paper, we study this SM approach more in depth and we propose a greatly improved attack on GeMSS based on this Support-Minors method. Even though GeMSS was already affected by [1], our attack affects it even more and makes it completely unfeasible to repair the scheme by simply increasing the size of its parameters or even applying the recent projection technique from [3] whose purpose was to make GeMSS immune to [1]. For instance, our attack on the GeMSS128 parameter set has estimated time complexity $2^{72}$, and repairing the scheme by applying [3] would result in a signature with slower signing time by an impractical factor of $2^{14}$. Another contribution is to suggest optimizations that can reduce memory access costs for an XL strategy on a large SM system using the Block-Wiedemann algorithm as subroutine when these costs are a concern. In a memory cost model based on [4], we show that the rectangular MinRank attack from [2] may indeed reduce the security for all Round 3 Rainbow parameter sets below their targeted security strengths, contradicting the lower bound claimed by [5] using the same memory cost model. ***** [1] Improved Key Recovery of the HFEv- Signature Scheme, Chengdong Tao and Albrecht Petzoldt and Jintai Ding, CRYPTO 2021. [2] Improved Cryptanalysis of UOV and Rainbow, Ward Beullens, EUROCRYPT 2021. [3] On the Effect of Projection on Rank Attacks in Multivariate Cryptography, Morten Øygarden and Daniel Smith-Tone and Javier Verbel, PQCrypto 2021. [4] NTRU Prime: Round 3 submission. [5] Rainbow Team: Response to recent paper by Ward Beullens. https://troll.iis. sinica.edu.tw/by-publ/recent/response-ward.pdf

In this paper, we show how to significantly improve algebraic techniques for solving the MinRank problem, which is ubiquitous in multivariate and rank metric code based cryptography. In the case of the structured MinRank instances arising in the latter, we build upon a recent breakthrough in Bardet et al. (EUROCRYPT 2020) showing that algebraic attacks outperform the combinatorial ones that were considered state of the art up until now. Through a slight modification of this approach, we completely avoid Gr\¨obner bases computations for certain parameters and are left only with solving linear systems. This does not only substantially improve the complexity, but also gives a convincing argument as to why algebraic techniques work in this case. When used against the second round NIST-PQC candidates ROLLO-I-128/192/256, our new attack has bit complexity respectively 71, 87, and 151, to be compared to 117, 144, and 197 as obtained in Bardet et al. (EUROCRYPT 2020). The linear systems arise from the nullity of the maximal minors of a certain matrix associated to the algebraic modeling. We also use a similar approach to improve the algebraic MinRank solvers for the usual MinRank problem. When applied against the second round NIST-PQC candidates GeMSS and Rainbow, our attack has a complexity that is very close to or even slightly better than those of the best known attacks so far. Note that these latter attacks did not rely on MinRank techniques since the MinRank approach used to give complexities that were far away from classical security levels.