Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

An Algebraic Attack on Rank Metric Code-Based Cryptosystems

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 real 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 or r + 1 depending on parameters, where r is the rank weight, which we show by extending results from Verbel et al. (PQCrypto 2019) who lower the solving degree to r + 2 in a similar context. We give complexity bounds for this approach as well as practical timings of an implementation using 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.
Liste complète des métadonnées

Littérature citée [57 références]  Voir  Masquer  Télécharger

https://hal-unilim.archives-ouvertes.fr/hal-02303015
Contributeur : Vincent Neiger <>
Soumis le : lundi 7 octobre 2019 - 10:19:18
Dernière modification le : jeudi 27 février 2020 - 01:56:10

Fichier

algebraic_attack_rankcbc.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-02303015, version 2

Collections

Citation

Magali Bardet, Pierre Briaud, Maxime Bros, Philippe Gaborit, Vincent Neiger, et al.. An Algebraic Attack on Rank Metric Code-Based Cryptosystems. Eurocrypt 2020, May 2020, Zagreb, Croatia. ⟨hal-02303015v2⟩

Partager

Métriques

Consultations de la notice

129

Téléchargements de fichiers

71