Polynomial Time Cryptanalysis of Noncommutative-Algebraic Key Exchange Protocols
Key Exchange Protocols (KEPs) make it possible for two electronic entities, Alice and Bob, to establish a shared secret key over a public communication channel. Since Diffie and Hellman's 1976 breakthrough KEP, few alternative KEP proposals resisted cryptanalysis. The authors introduce the linear centralizer method for a passive adversary to extract the shared key in group-theory based Key Exchange Protocols (KEPs). They apply this method to obtain a polynomial time cryptanalysis of the Commutator KEP, introduced by Anshel-Anshel-Goldfeld in 1999 and considered extensively ever since. They also apply this method to the Centralizer KEP, introduced by Shpilrain-Ushakov in 2006. Their method is proved to be of polynomial time using a technical lemma about sampling invertible matrices from a linear space of matrices.