Cryptology ePrint Archive: Report 2021/1677

Improving Support-Minors rank attacks: applications to G$e$MSS and Rainbow

John Baena and Pierre Briaud and Daniel Cabarcas and Ray Perlner and Daniel Smith-Tone and Javier Verbel

Abstract: 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 Tao at al. (CRYPTO 2021) and Beullens (EUROCRYPT 2021) 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 Ƙygarden et al. (PQCrypto 2021) as the signing time would be increased in a considerable way. Also, in our refined cost model, the rectangular MinRank attack from Beullens does indeed reduce the security of all Round 3 Rainbow parameter sets below their targeted security strengths.

Category / Keywords: public-key cryptography / Support-Minors, GeMSS, Rainbow, multivariate cryptography

Date: received 21 Dec 2021

Contact author: pierre briaud at inria fr , javier verbel at tii ae

Available format(s): PDF | BibTeX Citation

Version: 20211221:123044 (All versions of this report)

Short URL: ia.cr/2021/1677


[ Cryptology ePrint archive ]