Random Subgroups of Braid Groups: An Approach to Cryptanalysis of a Braid Group Based Cryptographic Protocol

摘要

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 with originally suggested parameters as well as with recently updated ones.