A Polynomial-Time Attack on the BBCRS Scheme

Abstract : The BBCRS scheme is a variant of the McEliece public-key encryption scheme where the hiding phase is performed by taking the inverse of a matrix which is of the form T+R where T is a sparse matrix with average row/column weight equal to a very small quantity m, usually m<2, and R is a matrix of small rank z⩾1. The rationale of this new transformation is the reintroduction of families of codes, like generalized Reed-Solomon codes, that are famously known for representing insecure choices. We present a key-recovery attack when z=1 and m is chosen between 1 and 1+R+O(1/\sqrt{n}) where R denotes the code rate. This attack has complexity O(n^6) and breaks all the parameters suggested in the literature.
Type de document :
Communication dans un congrès
Practice and Theory in Public-Key Cryptography - PKC 2015, Mar 2015, Washington, United States. LNCS
Liste complète des métadonnées

https://hal.archives-ouvertes.fr/hal-01104078
Contributeur : Alain Couvreur <>
Soumis le : vendredi 16 janvier 2015 - 09:53:34
Dernière modification le : mardi 5 juin 2018 - 10:14:25

Lien texte intégral

Identifiants

  • HAL Id : hal-01104078, version 1
  • ARXIV : 1501.03736

Citation

Alain Couvreur, Ayoub Otmani, Jean-Pierre Tillich, Valérie Gauthier-Umana. A Polynomial-Time Attack on the BBCRS Scheme. Practice and Theory in Public-Key Cryptography - PKC 2015, Mar 2015, Washington, United States. LNCS. 〈hal-01104078〉

Partager

Métriques

Consultations de la notice

392