A Polynomial-Time Attack on the BBCRS Scheme

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 $\mathbf{T}+\mathbf{R}$ where $\mathbf{T}$ is a sparse matrix with average row/column weight equal to a very small quantity $m$, usually $m<2$, and $\mathbf{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 representing insecure choices. We present a key-recovery attack when $z=1$ and $m$ is chosen between $1$ and $1+R+O(\frac{1}{\sqrt{n}})$ where $R$ denotes the code rate. This attack has complexity $O(n^6)$ and breaks all the parameters suggested in the literature.

Accepted to the conference Public Key Cryptography (PKC) 2015