International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Pierre Briaud , Inria Paris - Sorbonne Université
Javier Verbel , Cryptography Research Centre, Technology Innovation Institute
Daniel Smith--Tone , National Institute of Standards and Technology - University of Louisville
Ray Perlner , National Institute of Standards and Technology
Daniel Cabarcas , Universidad Nacional de Colombia
John Baena , Universidad Nacional de Colombia
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2022
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 [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.
Video from CRYPTO 2022
  title={Improving Support-Minors rank attacks: applications to GeMSS and Rainbow},
  author={Pierre Briaud and Javier Verbel and Daniel Smith--Tone and Ray Perlner and Daniel Cabarcas and John Baena},