International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

An Algebraic Attack on Rank Metric Code-Based Cryptosystems

Authors:
Magali Bardet , LITIS, University of Rouen Normandie, France, and Inria, 2 rue Simone Iff, 75012 Paris, France
Pierre Briaud , Inria, 2 rue Simone Iff, 75012 Paris, France
Maxime Bros , Univ. Limoges, CNRS, XLIM, UMR 7252, F-87000 Limoges, France
Philippe Gaborit , Univ. Limoges, CNRS, XLIM, UMR 7252, F-87000 Limoges, France
Vincent Neiger , Univ. Limoges, CNRS, XLIM, UMR 7252, F-87000 Limoges, France
Olivier Ruatta , Univ. Limoges, CNRS, XLIM, UMR 7252, F-87000 Limoges, France
Jean-Pierre Tillich , Inria, 2 rue Simone Iff, 75012 Paris, France
Download:
DOI: 10.1007/978-3-030-45727-3_3 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2020
Abstract: The Rank metric decoding problem is the main problem considered in cryptography based on codes in the rank metric. Very efficient schemes based on this problem or quasi-cyclic versions of it have been proposed recently, such as those in the submissions ROLLO and RQC currently at the second round of the NIST Post-Quantum Cryptography Standardization Process. While combinatorial attacks on this problem have been extensively studied and seem now well understood, the situation is not as satisfactory for algebraic attacks, for which previous work essentially suggested that they were ineffective for cryptographic parameters. In this paper, starting from Ourivski and Johansson's algebraic modelling of the problem into a system of polynomial equations, we show how to augment this system with easily computed equations so that the augmented system is solved much faster via Gröbner bases. This happens because the augmented system has solving degree $r$, $r+1$ or $r+2$ depending on the parameters, where $r$ is the rank weight, which we show by extending results from Verbel \emph{et al.} (PQCrypto 2019) on systems arising from the MinRank problem; with target rank $r$, Verbel \emph{et al.} lower the solving degree to $r+2$, and even less for some favorable instances that they call ``superdetermined''. We give complexity bounds for this approach as well as practical timings of an implementation using \texttt{magma}. This improves upon the previously known complexity estimates for both Gröbner basis and (non-quantum) combinatorial approaches, and for example leads to an attack in 200 bits on ROLLO-I-256 whose claimed security was 256 bits.
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30246,
  title={An Algebraic Attack on Rank Metric Code-Based Cryptosystems},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  keywords={Post-quantum cryptography;NIST-PQC candidates;rank metric code-based cryptography;algebraic cryptanalysis;Gr\\"obner basis},
  volume={12105},
  doi={10.1007/978-3-030-45727-3_3},
  author={Magali Bardet and Pierre Briaud and Maxime Bros and Philippe Gaborit and Vincent Neiger and Olivier Ruatta and Jean-Pierre Tillich},
  year=2020
}