Cryptanalysis via algebraic spans

Adi Ben-Zvi; Arkadius Kalka; Boaz Tsaban

Paper 2014/041

Cryptanalysis via algebraic spans

Adi Ben-Zvi, Arkadius Kalka, and Boaz Tsaban

Abstract

We introduce a method for obtaining provable polynomial time solutions of problems in nonabelian algebraic cryptography. This method is widely applicable, easier to apply, and more efficient than earlier methods. After demonstrating its applicability to the major classic nonabelian protocols, we use this method to cryptanalyze the Triple Decomposition key exchange protocol, the only classic group theory based key exchange protocol that could not be cryptanalyzed by earlier methods.

Note: Substantial extension of earlier version. Includes detailed specifications, complexity analyses, and experimental results. Introduction thoroughly revised.

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Keywords: nonabelian algebraic cryptography group theory-based cryptography braid-based cryptography Triple Decomposition key exchange Commutator key exchange Centralizer key exchange Braid Diffie--Hellman key exchange algebraic span cryptanalysis.
Contact author(s): tsaban @ math biu ac il
History: 2018-02-12: last of 2 revisions; 2014-01-15: received; See all versions
Short URL: https://ia.cr/2014/041
License: CC BY

BibTeX

@misc{cryptoeprint:2014/041,
      author = {Adi Ben-Zvi and Arkadius Kalka and Boaz Tsaban},
      title = {Cryptanalysis via algebraic spans},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/041},
      year = {2014},
      url = {https://eprint.iacr.org/2014/041}
}