Improving Support-Minors rank attacks: applications to GeMSS and Rainbow
Résumé
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, contradicting the lower bound claimed by [41] using the same memory cost model.
Domaines
Informatique [cs]
Fichier principal
GeMSS_sub.pdf (501.75 Ko)
Télécharger le fichier
GeMSS_sub (1).pdf (501.75 Ko)
Télécharger le fichier