Cryptology ePrint Archive: Report 2014/041

Cryptanalysis via algebraic spans

Adi Ben-Zvi and 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.

Category / 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.

Date: received 15 Jan 2014, last revised 12 Feb 2018

Contact author: tsaban at math biu ac il

Available format(s): PDF | BibTeX Citation

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

Version: 20180212:140924 (All versions of this report)

Short URL: ia.cr/2014/041


[ Cryptology ePrint archive ]