A polynomial-time attack on the BBCRS scheme

Alain Couvreur, Ayoub Otmani, Jean Pierre Tillich, Valérie Gauthier-Umaña

Resultado de la investigación: Capítulo en Libro/Reporte/ConferenciaContribución a la conferencia

10 Citas (Scopus)

Resumen

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 representin insecure choices. We present a key-recovery attack when z = 1 and m is chosen between 1 and 1+R+O(1/√n) where R denotes the code rate. This attack has complexity O(n6) and breaks all the parameters suggested in the literature.

Idioma originalInglés estadounidense
Título de la publicación alojadaPublic-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings
EditoresJonathan Katz
EditorialSpringer
Páginas175-193
Número de páginas19
ISBN (versión digital)9783662464465
DOI
EstadoPublicada - ene 1 2015
Evento18th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2015 - Gaithersburg, Estados Unidos
Duración: mar 30 2015abr 1 2015

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen9020
ISSN (versión impresa)0302-9743
ISSN (versión digital)1611-3349

Conferencia

Conferencia18th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2015
PaísEstados Unidos
CiudadGaithersburg
Período3/30/154/1/15

All Science Journal Classification (ASJC) codes

  • Ciencia computacional teórica
  • Informática (todo)

Huella Profundice en los temas de investigación de 'A polynomial-time attack on the BBCRS scheme'. En conjunto forman una huella única.

Citar esto