TY - GEN

T1 - A polynomial-time attack on the BBCRS scheme

AU - Couvreur, Alain

AU - Otmani, Ayoub

AU - Tillich, Jean Pierre

AU - Gauthier-Umaña, Valérie

PY - 2015/1/1

Y1 - 2015/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84925252708&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84925252708&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-46447-2_8

DO - 10.1007/978-3-662-46447-2_8

M3 - Conference contribution

AN - SCOPUS:84925252708

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 175

EP - 193

BT - Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings

A2 - Katz, Jonathan

PB - Springer

T2 - 18th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2015

Y2 - 30 March 2015 through 1 April 2015

ER -