Cryptanalysis of some nonabelian group-based key exchange protocols

Abstract 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. 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 discrete logarithm problem (DLP). In matrix groups over finite fields, we use the Jordan decomposition of a matrix to produce a polynomial time reduction of an A -restricted CSP, where A ⊆ G L n ( F q ) $A\subseteq {\mathrm{G}\mathrm{L} }_{n}\left({\mathbb{F}}_{q}\right)$ is a cyclic subgroup, to a set of O ( n 2 ) $\mathcal{O}\left({n}^{2}\right)$ DLPs over an extension of F q ${\mathbb{F}}_{q}$ . For polycyclic groups with two generators we show that the CSP where conjugators are restricted to a cyclic subgroup is either equivalent to a DLP in some ( Z / N Z ) * ${\left(\mathbb{Z}/N\mathbb{Z}\right)}^{{\ast}}$ or to an exponential diophantine integer equation. 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.