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 cryptographyNIST-PQC candidatesrank metric code-based cryptographyalgebraic 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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2022/1031}},
      url = {https://eprint.iacr.org/2022/1031}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.