Paper 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⩾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√) 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)
- 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
-
CC BY