Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

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

Published

Author(s)

John Bayron Baena Giraldo, Pierre Briaud, Daniel Cabarcas Jaramillo, Ray Perlner, Daniel Smith-Tone, 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 [9, 40] 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 [40], 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 [36] whose purpose was to make GeMSS immune to [40]. For instance, our attack on the GeMSS128 parameter set has estimated time complexity 2^72^ , and repairing the scheme by applying [36] 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 [7], we show that the rectangular MinRank attack from [9] may indeed reduce the security for all Round 3 Rainbow parameter sets below their targeted security strengths, contradicting the lower bound claimed by [41] using the same memory cost model.
Proceedings Title
Lecture Notes in Computer Science (LNCS): Advanced in Cryptology - Crypto 2022
Issue
13509
Conference Dates
August 15-18, 2022
Conference Location
Santa Barbara, CA, US
Conference Title
Crypto 2022

Keywords

Support-Minors, GeMSS, Rainbow, multivariate cryptography

Citation

Baena Giraldo, J. , Briaud, P. , Cabarcas Jaramillo, D. , Perlner, R. , Smith-Tone, D. and Verbel, J. (2022), Improving Support-Minors rank attacks: applications to GeMSS and Rainbow, Lecture Notes in Computer Science (LNCS): Advanced in Cryptology - Crypto 2022, Santa Barbara, CA, US, [online], https://doi.org/10.1007/978-3-031-15982-4_13, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=933540 (Accessed May 26, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created October 12, 2022, Updated April 17, 2024