Revisiting Algebraic Attacks on MinRank and on the Rank Decoding Problem

Magali Bardet; Pierre Briaud; Maxime Bros; Philippe Gaborit; Jean-Pierre Tillich

Paper 2022/1031

Revisiting Algebraic Attacks on MinRank and on the Rank Decoding Problem

Magali Bardet, Inria de Paris Research Centre, University of Rouen

Pierre Briaud, Inria de Paris Research Centre, Sorbonne University

Maxime Bros, University of Limoges

Philippe Gaborit, University of Limoges

Jean-Pierre Tillich, Inria de Paris Research Centre

Abstract

The Rank Decoding problem (RD) is at the core of rank-based cryptography. Cryptosystems such as ROLLO and RQC, which made it to the second round of the NIST Post-Quantum Standardization Process, as well as the Durandal signature scheme, rely on it or its variants. This problem can also be seen as a structured version of MinRank, which is ubiquitous in multivariate cryptography. Recently, [1,2] proposed attacks based on two new algebraic modelings, namely the MaxMinors modeling which is specific to RD and the Support-Minors modeling which applies to MinRank in general. Both improved significantly the complexity of algebraic attacks on these two problems. In the case of RD and contrarily to what was believed up to now, these new attacks were shown to be able to outperform combinatorial attacks and this even for very small field sizes. However, we prove here that the analysis performed in [2] for one of these attacks which consists in mixing the MaxMinors modeling with the Support-Minors modeling to solve RD is too optimistic and leads to underestimate the overall complexity. This is done by exhibiting linear dependencies between these equations and by considering an Fqm version of these modelings which turns out to be instrumental for getting a better understanding of both systems. Moreover, by working over Fqm rather than over Fq, we are able to drastically reduce the number of variables in the system and we (i) still keep enough algebraic equations to be able to solve the system, (ii) are able to analyze rigorously the complexity of our approach. This new approach may improve the older MaxMinors approach on RD from [1,2] for certain parameters. We also introduce a new hybrid approach on the Support-Minors system whose impact is much more general since it applies to any MinRank problem. This technique improves significantly the complexity of the Support-Minors approach for small to moderate field sizes. References: [1] An Algebraic Attack on Rank Metric Code-Based Cryptosystems, Bardet, Briaud, Bros, Gaborit, Neiger, Ruatta, Tillich, EUROCRYPT 2020. [2] Improvements of Algebraic Attacks for solving the Rank Decoding and MinRank problems, Bardet, Bros, Cabarcas, Gaborit, Perlner, Smith-Tone, Tillich, Verbel, ASIACRYPT 2020.

Note: Minor revision

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: Post-quantum cryptography NIST-PQC candidates rank metric code-based cryptography algebraic attacks
Contact author(s): pierre briaud @ inria fr
maxime bros @ unilim fr
History: 2023-06-14: last of 2 revisions; 2022-08-09: received; See all versions
Short URL: https://ia.cr/2022/1031
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1031,
      author = {Magali Bardet and Pierre Briaud and Maxime Bros and Philippe Gaborit and Jean-Pierre Tillich},
      title = {Revisiting Algebraic Attacks on {MinRank} and on the Rank Decoding Problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1031},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1031}
}