International Association
for Cryptologic Research

We provide new provable polynomial time solutions

of a number of problems in noncommutative-algebraic cryptography.

In contrast to the linear centralizer method of \\cite{LinCent}, the new method is

very simple: In order to solve linear equations on matrices

restricted to matrix groups, solve them over the generated

algebras. We name this approach the \\emph{algebraic span method}.

The resulting algorithms are have substantially better performance than those of \\cite{LinCent}.

These algorithms constitute cryptanalyses of the motivating protocols that

cannot be foiled by changing the distributions used in the protocols, and are

practical for most affordable parameter settings.