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.
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 language | English |
---|---|
Pages (from-to) | 33-43 |
Number of pages | 11 |
Journal | Groups Complexity Cryptology |
Volume | 9 |
Issue number | 1 |
DOIs | |
Publication status | Published - 2015 |