Related Experiment Videos
Cryptanalysis of some nonabelian group-based key exchange protocols
Simran Tinani1, Carlo Matteotti2, Joachim Rosenthal1
1Institute of Mathematics, University of Zurich, Winterthurerstrasse 190, 8057 Zurich, Switzerland.
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 is a cyclic subgroup, to a set of DLPs over an extension of . 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 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.
Related Concept Videos
Norton's Theorem
Net Change Theorem
Protecting Groups for Aldehydes and Ketones: Introduction
Fundamental Theorem of Algebra
Second Uniqueness Theorem
In contrast, consider that the electric field is non-unique and apply Gauss's law in divergence form in the region between the conductors and the integral form to the surface...
Castigliano's Theorem