2012/10/31 by Boaz Tsaban · 69 citations
Computer Science · Mathematics · #Advanced Algebra and Geometry #Algebra over a field #Algorithm #Coding theory and cryptography #Commutator #Computer science #Computer security #Cryptanalysis #Cryptographic protocol #Cryptography #Discrete mathematics #Encryption #Geometric and Algebraic Topology #Key (lock) #Key exchange #Mathematics #Polynomial #Public-key cryptography #Pure mathematics #Theoretical computer science #Time complexity #cs.CR #math.GR #math.RT
paper · pdf · doi:10.1007/s00145-013-9170-9
published in Journal of Cryptology 28(3), 601-622 (Springer Science+Business Media) · Minor changes. Now published
openalex publication_date 2013/11/14 · arxiv created 2015/06/17 · arxiv updated 2015/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We introduce the 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 Commutator key exchange protocol is based. We also apply this method to the computational problem underlying the 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.