Paper 2012/615

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.

Note: Comments are welcome.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Braid group cryptographynon-commutative cryptographyCommutator Key Exchangekey exchange protocolsLas Vegas polynomial time cryptanalysis
Contact author(s)
tsaban @ math biu ac il
History
2013-01-28: revised
2012-11-01: received
See all versions
Short URL
https://ia.cr/2012/615
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/615,
      author = {Boaz Tsaban},
      title = {Polynomial time solutions of computational problems  in noncommutative-algebraic cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2012/615},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/615}},
      url = {https://eprint.iacr.org/2012/615}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.