A polynomial-time attack on the BBCRS scheme

Alain Couvreur; Ayoub Otmani; Jean Pierre Tillich; Valérie Gauthier-Umaña

doi:10.1007/978-3-662-46447-2_8

A polynomial-time attack on the BBCRS scheme

Alain Couvreur
, Ayoub Otmani
, Jean Pierre Tillich
, Valérie Gauthier-Umaña

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 representin insecure choices. We present a key-recovery attack when z = 1 and m is chosen between 1 and 1+R+O(1/√n) where R denotes the code rate. This attack has complexity O(n⁶) and breaks all the parameters suggested in the literature.

Original language	English
Title of host publication	Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings
Editors	Jonathan Katz
Publisher	Springer Verlag
Pages	175-193
Number of pages	19
ISBN (Electronic)	9783662464465
DOIs	https://doi.org/10.1007/978-3-662-46447-2_8
Publication status	Published - 1 Jan 2015
Event	18th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2015 - Gaithersburg, United States Duration: 30 Mar 2015 → 1 Apr 2015

Publication series

Name	Lecture Notes in Computer Science
Volume	9020
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	18th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2015
Country/Territory	United States
City	Gaithersburg
Period	30/03/15 → 1/04/15

Keywords

Code-based cryptography
Component-wise product of codes
Distinguisher
Generalized Reed-Solomon codes
Key-recovery

Access to Document

10.1007/978-3-662-46447-2_8

Cite this

Couvreur, A., Otmani, A., Tillich, J. P., & Gauthier-Umaña, V. (2015). A polynomial-time attack on the BBCRS scheme. In J. Katz (Ed.), Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings (pp. 175-193). (Lecture Notes in Computer Science; Vol. 9020). Springer Verlag. https://doi.org/10.1007/978-3-662-46447-2_8

@inproceedings{c7d2a92675164c90a27f078deb5febf9,

title = "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 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 representin insecure choices. We present a key-recovery attack when z = 1 and m is chosen between 1 and 1+R+O(1/√n) where R denotes the code rate. This attack has complexity O(n6) and breaks all the parameters suggested in the literature.",

keywords = "Code-based cryptography, Component-wise product of codes, Distinguisher, Generalized Reed-Solomon codes, Key-recovery",

author = "Alain Couvreur and Ayoub Otmani and Tillich, \{Jean Pierre\} and Val{\'e}rie Gauthier-Uma{\~n}a",

note = "Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2015.; 18th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2015 ; Conference date: 30-03-2015 Through 01-04-2015",

year = "2015",

month = jan,

day = "1",

doi = "10.1007/978-3-662-46447-2\_8",

language = "English",

series = "Lecture Notes in Computer Science",

publisher = "Springer Verlag",

pages = "175--193",

editor = "Jonathan Katz",

booktitle = "Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings",

}

Couvreur, A, Otmani, A, Tillich, JP & Gauthier-Umaña, V 2015, A polynomial-time attack on the BBCRS scheme. in J Katz (ed.), Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. Lecture Notes in Computer Science, vol. 9020, Springer Verlag, pp. 175-193, 18th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2015, Gaithersburg, United States, 30/03/15. https://doi.org/10.1007/978-3-662-46447-2_8

A polynomial-time attack on the BBCRS scheme. / Couvreur, Alain; Otmani, Ayoub; Tillich, Jean Pierre et al.
Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. ed. / Jonathan Katz. Springer Verlag, 2015. p. 175-193 (Lecture Notes in Computer Science; Vol. 9020).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A polynomial-time attack on the BBCRS scheme

AU - Couvreur, Alain

AU - Otmani, Ayoub

AU - Tillich, Jean Pierre

AU - Gauthier-Umaña, Valérie

N1 - Publisher Copyright: © International Association for Cryptologic Research 2015.

PY - 2015/1/1

Y1 - 2015/1/1

N2 - 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 representin insecure choices. We present a key-recovery attack when z = 1 and m is chosen between 1 and 1+R+O(1/√n) where R denotes the code rate. This attack has complexity O(n6) and breaks all the parameters suggested in the literature.

AB - 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 representin insecure choices. We present a key-recovery attack when z = 1 and m is chosen between 1 and 1+R+O(1/√n) where R denotes the code rate. This attack has complexity O(n6) and breaks all the parameters suggested in the literature.

KW - Code-based cryptography

KW - Component-wise product of codes

KW - Distinguisher

KW - Generalized Reed-Solomon codes

KW - Key-recovery

UR - https://www.scopus.com/pages/publications/84925252708

U2 - 10.1007/978-3-662-46447-2_8

DO - 10.1007/978-3-662-46447-2_8

M3 - Conference contribution

AN - SCOPUS:84925252708

T3 - Lecture Notes in Computer Science

SP - 175

EP - 193

BT - Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings

A2 - Katz, Jonathan

PB - Springer Verlag

T2 - 18th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2015

Y2 - 30 March 2015 through 1 April 2015

ER -

A polynomial-time attack on the BBCRS scheme

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this