Cryptology ePrint Archive: Report 2016/302

A Polynomial-Time Attack on the BBCRS Scheme

Alain Couvreur and Ayoub Otmani and 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.

Category / Keywords: public-key cryptography / cryptanalysis, code-based cryptography, McEliece, distinguisher, filtration attack

Original Publication (with major differences): IACR-PKC--1

Date: received 16 Mar 2016, last revised 16 Mar 2016

Contact author: alain couvreur at lix polytechnique fr

Available format(s): PDF | BibTeX Citation

Version: 20160317:162650 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]