Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / noncommutative cryptography, Commutator key exchange

Date: received 15 Jan 2014

Contact author: tsaban at math biu ac il

Available format(s): PDF | BibTeX Citation

Note: Preliminary announcement. Comments and suggestions are welcome.

Version: 20140115:201530 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]