MarriageTheoremのこと

_ arXiv:math 10月18日分まで、IACR ePrint 2012/618まで確認済み

_ 気になった論文：Polynomial time cryptanalysis of noncommutative-algebraic key exchange protocols, Boaz Tsaban, http://eprint.iacr.org/2012/615

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.