Improving Support-Minors rank attacks: applications to GeMSS and Rainbow

John Baena (1) , Pierre Briaud (2, 3) , Daniel Cabarcas (1) , Ray Perlner (4) , Daniel Smith-Tone (4, 5) , Javier Verbel (6)

1 Universidad Nacional de Colombia Sede Medellín
2 COSMIQ - Cryptologie symétrique, cryptologie fondée sur les codes et information quantique
3 UFR 919 - Sorbonne Université - UFR d'Ingénierie
4 NIST - National Institute of Standards and Technology [Gaithersburg]
5 University of Louisville
6 TII - Technology Innovation Institute

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 [35] and [7] on the NIST candidates GeMSS and Rainbow respectively. In this paper, we study this SM approach more in depth, which allows us first to propose a greatly improved attack on GeMSS and also to define a more realistic cost model to evaluate the memory complexity of an XL strategy on the SM system using the Block-Wiedemann algorithm. Our new attack on GeMSS makes it completely unfeasible to repair the scheme by simply increasing the size of its parameters or even applying the projection technique from [31], as the signing time would be increased in a considerable way. Also, in our refined cost model, the rectangular MinRank attack from [7] does indeed reduce the security of all Round 3 Rainbow parameter sets below their targeted security strengths.

Mots clés: Support-Minors; GeMSS; Rainbow; Multivariate cryptography

Domaines: Informatique [cs]

John Baena, Pierre Briaud, Daniel Cabarcas, Ray Perlner, Daniel Smith-Tone, et al.. Improving Support-Minors rank attacks: applications to GeMSS and Rainbow. 2022. ⟨hal-03533455v1⟩