Improving Support-Minors Rank Attacks: Applications to GeMSS and Rainbow

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 on the Round 3 NIST candidates G𝑒MSS and Rainbow respectively. In this paper, we study this SM approach more in depth and we propose a greatly improved attack on G𝑒MSS based on this Support-Minors method. Even though G𝑒MSS was already affected by, 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 whose purpose was to make G𝑒MSS immune to. For instance, our attack on the G𝑒MSS128 parameter set has estimated time complexity 2⁷², and repairing the scheme by applying would result in a signature with slower signing time by an impractical factor of 2¹⁴. 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, we show that the rectangular MinRank attack from may indeed reduce the security for all Round 3 Rainbow parameter sets below their targeted security strengths, contradicting the lower bound claimed by using the same memory cost model.