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

urosario

Research output: Chapter in Book/Inform › Conference contribution

19 Scopus citations

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 (US)
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
Pages	175-193
Number of pages	19
ISBN (Electronic)	9783662464465
DOIs	https://doi.org/10.1007/978-3-662-46447-2_8
State	Published - Jan 1 2015
Event	18th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2015 - Gaithersburg, United States Duration: Mar 30 2015 → Apr 1 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
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	3/30/15 → 4/1/15

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

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 (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9020). Springer. https://doi.org/10.1007/978-3-662-46447-2_8

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

@inproceedings{d608d608da0246dab6835067f41f8e7f,

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.",

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

year = "2015",

month = jan,

day = "1",

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

language = "English (US)",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

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",

address = "Germany",

note = "18th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2015 ; Conference date: 30-03-2015 Through 01-04-2015",

}

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 (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9020, Springer, pp. 175-193, 18th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2015, Gaithersburg, United States, 3/30/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, 2015. p. 175-193 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9020).

Research output: Chapter in Book/Inform › Conference contribution

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

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.

UR - http://www.scopus.com/inward/record.url?scp=84925252708&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84925252708&partnerID=8YFLogxK

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 (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

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

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

Y2 - 30 March 2015 through 1 April 2015

ER -

Couvreur A, Otmani A, Tillich JP, Gauthier-Umaña V. A polynomial-time attack on the BBCRS scheme. In Katz J, editor, Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. Springer. 2015. p. 175-193. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-46447-2_8

A polynomial-time attack on the BBCRS scheme

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this