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 -