Length-based attacks in polycyclic groups

Delaram Kahrobaei, David Garber, Ha Lam

Research output: Contribution to journalArticlepeer-review

Abstract

The Anshel–Anshel–Goldfeld (AAG) key-exchange protocol was implemented and studied with
the braid groups as its underlying platform. The length-based attack, introduced by Hughes and Tannenbaum,
has been used to cryptanalyze the AAG protocol in this setting. Eick and Kahrobaei suggest to use the
polycyclic groups as a possible platform for the AAG protocol. In this paper, we apply several known variants
of the length-based attack against the AAG protocol with the polycyclic group as the underlying platform.
The experimental results show that, in these groups, the implemented variants of the length-based attack are
unsuccessful in the case of polycyclic groups having high Hirsch length. This suggests that the length-based
attack is insucient to cryptanalyze the AAG protocol when implemented over this type of polycyclic groups.
This implies that polycyclic groups could be a potential platform for some cryptosystems based on conjugacy
search problem, such as non-commutative Die–Hellman, El Gamal and Cramer–Shoup key-exchange protocols.
Moreover, we compare for the rst time the success rates of the dierent variants of the length-based
attack. These experiments show that, in these groups, the memory length-based attack introduced by Garber,
Kaplan, Teicher, Tsaban and Vishne does better than the other variants proposed thus far in this context.
Original languageEnglish
Pages (from-to)33-43
Number of pages11
JournalGroups Complexity Cryptology
Volume9
Issue number1
DOIs
Publication statusPublished - 2015

Cite this