By the same authors

From the same journal

Length-based attacks in polycyclic groups

Research output: Contribution to journalArticle

Full text download(s)

  • LBA

    518 KB, PDF document

Published copy (DOI)



Publication details

JournalGroups Complexity Cryptology
DatePublished - 2015
Issue number1
Number of pages11
Pages (from-to)33-43
Original languageEnglish


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.

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations