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

Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

23 Scopus citations

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.

Original languageEnglish
Title of host publicationPublic Key Cryptography - PKC 2006 - 9th International Conference on Theory and Practice in Public-Key Cryptography, Proceedings
Pages302-314
Number of pages13
DOIs
StatePublished - 2006
Event9th International Conference on Theory and Practice in Public-Key Cryptography, PKC 2006 - New York, NY, United States
Duration: 24 Apr 200626 Apr 2006

Publication series

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

Conference

Conference9th International Conference on Theory and Practice in Public-Key Cryptography, PKC 2006
Country/TerritoryUnited States
CityNew York, NY
Period24/04/0626/04/06

Fingerprint

Dive into the research topics of 'Random subgroups of braid groups: An approach to cryptanalysis of a braid group based cryptographic protocol'. Together they form a unique fingerprint.

Cite this