Paper 2014/041

Practical polynomial time solutions of several major problems in noncommutative-algebraic cryptography

Boaz Tsaban

Abstract

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.

Note: Preliminary announcement. Comments and suggestions are welcome.