Paper 2014/041

Cryptanalysis via algebraic spans

Adi Ben-Zvi and Arkadius Kalka and Boaz Tsaban

Abstract

We describe a new method for obtaining polynomial time solutions of problems in noncommutative algebraic cryptography. This method is easier to apply and more efficient than the linear centralizer method. We use it to provide a cryptanalysis of the Triple Decompostion key exchange protocol, the only classic group theory based key exchange protocol that was not cryptanalyzed thus far.

Note: Substantial revision. New material added.