On the Cryptanalysis of the Generalized Simultaneous Conjugacy Search Problem and the Security of the Algebraic Eraser
The Algebraic Eraser (AE) is a cryptographic primitive that can be used to obscure information in certain algebraic cryptosystems. The Colored Burau Key Agreement Protocol (CBKAP), which is built on the AE, was introduced by I. Anshel, M. Anshel, D. Goldfeld, and S. Lemieux in 2006 as a protocol suitable for use on platforms with constrained computational resources, such as RFID and wireless sensors. In 2009 A. Myasnikov and A. Ushnakov proposed an attack on CBKAP that attempts to defeat the generalized simultaneous conjugacy search problem, which is the public-key computational problem underlying CBKAP. In this paper, the authors investigate the effectiveness of this attack.