*18:17*[Pub][ePrint] Polynomial time cryptanalysis of noncommutative-algebraic key exchange protocols, by Boaz Tsaban

We introduce the \\emph{linear centralizer method} for a passive adversary

to extract the shared key in group-theory based key exchange protocols (KEPs).

We apply this method to obtain a polynomial time cryptanalysis of the

\\emph{Commutator KEP}, introduced by Anshel--Anshel--Goldfeld in 1999 and considered

extensively ever since.

We also apply this method to the \\emph{Centralizer KEP}, introduced by Shpilrain--Ushakov in 2006.

Our method is proved to be of polynomial time using a technical lemma

about sampling invertible matrices from a linear space of matrices.