Cryptanalysis of some Nonabelian Group-Based Key Exchange Protocols

In the recently emerging field of nonabelian group-based cryptography, a prominently used one-way function is the Conjugacy Search Problem (CSP), and two important classes of platform groups are polycyclic and matrix groups. In this paper, we discuss the complexity of the conjugacy search problem (CSP) in these two classes of platform groups using the three protocols in [10], [26], and [29] as our starting point. We produce a polynomial time solution for the CSP in a finite polycyclic group with two generators, and show that a restricted CSP is reducible to a DLP. In matrix groups over finite fields, we usedthe Jordan decomposition of a matrix to produce a polynomial time reduction of an A-restricted CSP, where A is a cyclic subgroup of the general linear group, to a set of DLPs over an extension of Fq. We use these general methods and results to describe concrete cryptanalysis algorithms for these three systems. In particular, we show that in the group of invertible matrices over finite fields and in polycyclic groups with two generators, a CSP where conjugators are restricted to a cyclic subgroup is reducible to a set of O(n2) discrete logarithm problems. Using our general results, we demonstrate concrete cryptanalysis algorithms for each of these three schemes. We believe that our methods and findings are likely to allow for several other heuristic attacks in the general case.