**Polynomial time solutions of computational problems in noncommutative-algebraic cryptography**

*Boaz Tsaban*

**Abstract: **We introduce the \emph{linear centralizer method},
and use it to devise a provable polynomial time solution
of the Commutator Key Exchange Problem, the computational
problem on which, in the passive adversary model,
the security of the Anshel--Anshel--Goldfeld 1999 \emph{Commutator} key exchange protocol is based.
We also apply this method to the computational problem underlying the \emph{Centralizer} key exchange protocol,
introduced by Shpilrain and Ushakov in 2006.

This is the first provable polynomial time cryptanalysis of the Commutator key exchange protocol, hitherto the most important key exchange protocol in the realm of noncommutative-algebraic cryptography, and the first cryptanalysis (of any kind) of the Centralizer key exchange protocol. Unlike earlier cryptanalyses of the Commutator key exchange protocol, our cryptanalyses cannot be foiled by changing the distributions used in the protocol.

**Category / Keywords: **public-key cryptography / Braid group cryptography, non-commutative cryptography, Commutator Key Exchange, key exchange protocols, Las Vegas polynomial time cryptanalysis

**Date: **received 30 Oct 2012, last revised 28 Jan 2013

**Contact author: **tsaban at math biu ac il

**Available format(s): **PDF | BibTeX Citation

**Note: **Comments are welcome.

**Version: **20130128:220601 (All versions of this report)

**Short URL: **ia.cr/2012/615

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]