文摘
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 \(\varvec{T}+ \varvec{R}\) where \(\varvec{T}\) is a sparse matrix with average row/column weight equal to a very small quantity \(m\) , usually \(m , and \(\varvec{R}\) is a matrix of small rank \(z\ge 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(\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.