Paper 2016/302

A Polynomial-Time Attack on the BBCRS Scheme

Alain Couvreur, Ayoub Otmani, Jean-Pierre Tillich, and Valérie Gauthier-Umana

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&#10878;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(1n&#8730;) where R denotes the code rate. This attack has complexity O(n6) and breaks all the parameters suggested in the literature.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR.Major revision. IACR-PKC--1
Keywords
cryptanalysiscode-based cryptographyMcEliecedistinguisherfiltration attack
Contact author(s)
alain couvreur @ lix polytechnique fr
History
2016-03-17: received
Short URL
https://ia.cr/2016/302
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/302,
      author = {Alain Couvreur and Ayoub Otmani and Jean-Pierre Tillich and Valérie Gauthier-Umana},
      title = {A Polynomial-Time Attack on the BBCRS Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2016/302},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/302}},
      url = {https://eprint.iacr.org/2016/302}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.