Random subgroups of braid groups: An approach to cryptanalysis of a braid group based cryptographic protocol

Alexei Myasnikov; Vladimir Shpilrain; Alexander Ushakov

doi:10.1007/11745853_20

Random subgroups of braid groups: An approach to cryptanalysis of a braid group based cryptographic protocol

Alexei Myasnikov
, Vladimir Shpilrain
, Alexander Ushakov

Department of Mathematical Sciences

City University of New York

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

23 Scopus citations

Abstract

Motivated by cryptographic applications, we study subgroups of braid groups B_n generated by a small number of random elements of relatively small lengths compared to n. Our experiments show that "most" of these subgroups are equal to the whole B_n, and "almost all" of these subgroups are generated by positive braid words. We discuss the impact of these experimental results on the security of the Anshel-Anshel-Goldfeld key exchange protocol [2] with originally suggested parameters as well as with recently updated ones.

Original language	English
Title of host publication	Public Key Cryptography - PKC 2006 - 9th International Conference on Theory and Practice in Public-Key Cryptography, Proceedings
Pages	302-314
Number of pages	13
DOIs	https://doi.org/10.1007/11745853_20
State	Published - 2006
Event	9th International Conference on Theory and Practice in Public-Key Cryptography, PKC 2006 - New York, NY, United States Duration: 24 Apr 2006 → 26 Apr 2006

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3958 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th International Conference on Theory and Practice in Public-Key Cryptography, PKC 2006
Country/Territory	United States
City	New York, NY
Period	24/04/06 → 26/04/06

Access to Document

10.1007/11745853_20

Cite this

Myasnikov, A., Shpilrain, V., & Ushakov, A. (2006). Random subgroups of braid groups: An approach to cryptanalysis of a braid group based cryptographic protocol. In Public Key Cryptography - PKC 2006 - 9th International Conference on Theory and Practice in Public-Key Cryptography, Proceedings (pp. 302-314). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3958 LNCS). https://doi.org/10.1007/11745853_20

Myasnikov, Alexei ; Shpilrain, Vladimir ; Ushakov, Alexander. / Random subgroups of braid groups : An approach to cryptanalysis of a braid group based cryptographic protocol. Public Key Cryptography - PKC 2006 - 9th International Conference on Theory and Practice in Public-Key Cryptography, Proceedings. 2006. pp. 302-314 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{5da9be7a71a646e29c5e023849006a77,

title = "Random subgroups of braid groups: An approach to cryptanalysis of a braid group based cryptographic protocol",

abstract = "Motivated by cryptographic applications, we study subgroups of braid groups Bn generated by a small number of random elements of relatively small lengths compared to n. Our experiments show that {"}most{"} of these subgroups are equal to the whole Bn, and {"}almost all{"} of these subgroups are generated by positive braid words. We discuss the impact of these experimental results on the security of the Anshel-Anshel-Goldfeld key exchange protocol [2] with originally suggested parameters as well as with recently updated ones.",

author = "Alexei Myasnikov and Vladimir Shpilrain and Alexander Ushakov",

year = "2006",

doi = "10.1007/11745853\_20",

language = "English",

isbn = "3540338519",

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

pages = "302--314",

booktitle = "Public Key Cryptography - PKC 2006 - 9th International Conference on Theory and Practice in Public-Key Cryptography, Proceedings",

note = "9th International Conference on Theory and Practice in Public-Key Cryptography, PKC 2006 ; Conference date: 24-04-2006 Through 26-04-2006",

}

Myasnikov, A, Shpilrain, V & Ushakov, A 2006, Random subgroups of braid groups: An approach to cryptanalysis of a braid group based cryptographic protocol. in Public Key Cryptography - PKC 2006 - 9th International Conference on Theory and Practice in Public-Key Cryptography, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3958 LNCS, pp. 302-314, 9th International Conference on Theory and Practice in Public-Key Cryptography, PKC 2006, New York, NY, United States, 24/04/06. https://doi.org/10.1007/11745853_20

Random subgroups of braid groups: An approach to cryptanalysis of a braid group based cryptographic protocol. / Myasnikov, Alexei; Shpilrain, Vladimir; Ushakov, Alexander.
Public Key Cryptography - PKC 2006 - 9th International Conference on Theory and Practice in Public-Key Cryptography, Proceedings. 2006. p. 302-314 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3958 LNCS).

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

TY - GEN

T1 - Random subgroups of braid groups

T2 - 9th International Conference on Theory and Practice in Public-Key Cryptography, PKC 2006

AU - Myasnikov, Alexei

AU - Shpilrain, Vladimir

AU - Ushakov, Alexander

PY - 2006

Y1 - 2006

N2 - Motivated by cryptographic applications, we study subgroups of braid groups Bn generated by a small number of random elements of relatively small lengths compared to n. Our experiments show that "most" of these subgroups are equal to the whole Bn, and "almost all" of these subgroups are generated by positive braid words. We discuss the impact of these experimental results on the security of the Anshel-Anshel-Goldfeld key exchange protocol [2] with originally suggested parameters as well as with recently updated ones.

AB - Motivated by cryptographic applications, we study subgroups of braid groups Bn generated by a small number of random elements of relatively small lengths compared to n. Our experiments show that "most" of these subgroups are equal to the whole Bn, and "almost all" of these subgroups are generated by positive braid words. We discuss the impact of these experimental results on the security of the Anshel-Anshel-Goldfeld key exchange protocol [2] with originally suggested parameters as well as with recently updated ones.

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

UR - https://www.scopus.com/pages/publications/33745819514#tab=citedBy

U2 - 10.1007/11745853_20

DO - 10.1007/11745853_20

M3 - Conference contribution

AN - SCOPUS:33745819514

SN - 3540338519

SN - 9783540338512

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 302

EP - 314

BT - Public Key Cryptography - PKC 2006 - 9th International Conference on Theory and Practice in Public-Key Cryptography, Proceedings

Y2 - 24 April 2006 through 26 April 2006

ER -

Myasnikov A, Shpilrain V, Ushakov A. Random subgroups of braid groups: An approach to cryptanalysis of a braid group based cryptographic protocol. In Public Key Cryptography - PKC 2006 - 9th International Conference on Theory and Practice in Public-Key Cryptography, Proceedings. 2006. p. 302-314. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11745853_20

Random subgroups of braid groups: An approach to cryptanalysis of a braid group based cryptographic protocol

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this