Cryptanalysis on braid cryptosystem via the Krammer representation

Abstract

In 2000, a new public-key cryptosystem using braid groups is proposed. The system is based on the Diffie-Hellman type Conjugacy Problem(DHCP) and DHCP is in turn based on a version of conjugator search problem. Representation theory of braid groups into matrix groups or algebras have been studied extensively. In particular braid groups are linear, that is, there is a faithful representation into a general linear group and there are also other representations that are closed to be faithful. Thus the search problems in braid group can be transformed to systems of linear equations via representations. In this thesis, we analysis the feasibility of this approach of linear algebra via mainly Lawrence-Krammer representation. Besides its faithfulness, Lawrence-Krammer representation enjoys the property that its inverse can be computed easily. We propose a deterministic algorithm for DHCP that has the running time Ο(n^16(log n)^2) for the braid index n. And we conclude that a solution to DHCP via Lawrence-Krammer representation is not yet practical for the proposed parameter in 2000. We also compute the complexity of our algorithm for the system of linear equations when Burau representation is used instead. For random instances, our approach may directly solve a harder low-level problem called the decomposition problem.