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

INRIA
LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes
INRIA Institut National de Recherche en Informatique et en Automatique
Department of Mathematics
Universidad del Rosario

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

28 Citations (Scopus)

Résumé

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.

langue originale	Anglais
titre	Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings
rédacteurs en chef	Jonathan Katz
Editeur	Springer Verlag
Pages	175-193
Nombre de pages	19
ISBN (Electronique)	9783662464465
Les DOIs	https://doi.org/10.1007/978-3-662-46447-2_8
état	Publié - 1 janv. 2015
Evénement	18th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2015 - Gaithersburg, États-Unis Durée: 30 mars 2015 → 1 avr. 2015

Série de publications

Nom	Lecture Notes in Computer Science
Volume	9020
ISSN (imprimé)	0302-9743
ISSN (Electronique)	1611-3349

Une conférence

Une conférence	18th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2015
Pays/Territoire	États-Unis
La ville	Gaithersburg
période	30/03/15 → 1/04/15

Accès au document

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

Contient cette citation

Couvreur, A., Otmani, A., Tillich, J. P., & Gauthier-Umaña, V. (2015). A polynomial-time attack on the BBCRS scheme. Dans J. Katz (Ed.), Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings (p. 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. Dans 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, p. 175-193, 18th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2015, Gaithersburg, États-Unis, 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).

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

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

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

Résumé

Série de publications

Une conférence

Accès au document

Empreinte digitale

Contient cette citation