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.

Improvements of Algebraic Attacks for solving the Rank Decoding and MinRank problems

Published

Author(s)

Magali Bardet, Maxime Bros, Daniel Cabarcas, Philippe Gaborit, Ray Perlner, Daniel Smith-Tone, Jean-Pierre Tillich, Javier Verbel

Abstract

In this paper, we show how to significantly improve algebraic techniques for solving the MinRank problem, which is ubiquitous in multivariate and rank metric code based cryptography. In the case of the structured MinRank instances arising in the latter, we build upon a recent breakthrough showing that algebraic attacks outperform the combinatorial ones that were considered state of the art up until now. Through a slight modification of this approach, we completely avoid Gröbner bases computations for certain parameters and are left only with solving linear systems. This does not only substantially improve the complexity, but also gives a convincing argument as to why algebraic techniques work in this case. When used against the second round NIST-PQC candidates ROLLO-I- 128/192/256, our new attack has bit complexity respectively 71, 87, and 151, to be compared to 117, 144, and 197 as obtained in. The linear systems arise from the nullity of the maximal minors of a certain matrix associated to the algebraic modeling. We also use a similar approach to improve the algebraic MinRank solvers for the usual MinRank problem. When applied against the second round NIST-PQC candidates GeMSS and Rainbow, our attack has a complexity that is very close to or even slightly better than those of the best known attacks so far. Note that these latter attacks did not rely on MinRank techniques since the MinRank approach used to give complexities that were far away from classical security levels.
Proceedings Title
Advances in Cryptology – ASIACRYPT 2020
Volume
12491
Conference Dates
December 7-11, 2020
Conference Location
Kobe,
Conference Title
Asiacrypt 2020

Keywords

Post-quantum cryptography, NIST-PQC candidates , rankmetric code-based cryptography , algebraic attack

Citation

Bardet, M. , Bros, M. , Cabarcas, D. , Gaborit, P. , Perlner, R. , Smith-Tone, D. , Tillich, J. and Verbel, J. (2020), Improvements of Algebraic Attacks for solving the Rank Decoding and MinRank problems, Advances in Cryptology – ASIACRYPT 2020, Kobe, , [online], https://doi.org/10.1007/978-3-030-64837-4_17, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=930046 (Accessed July 26, 2021)
Created December 6, 2020, Updated March 22, 2021