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.
2000년에 땋임군을 이용한 새로운 공개키 암호체계가 고안되었다. 이 암호체계는 Diffie-Hellman 형식의 공액문제에 기반을 두고 있다. 하지만 땋임군은 충실한 재표현인 크래머 재표현을 가지고 있고, 이것을 이용하면 땋임군의 공액 문제를 두 변수 다항식을 원소로 갖는 선형 대수의 문제로 변환할 수 있다.
이 논문에서는 먼저 Diffie-Hellman 문제의 조건을 만족하는 땋임의 크래머 재표현이 특별한 형태를 가진다는 것을 보임으로써 문제를 축소하고, 다항식을 원소로 갖는 선형 방정식을 효과적으로 푸는 방법을 제시한다. 그리고 이것을 이용하여 Diffie-Hellman 형식의 공액문제를 풀고 그것의 복잡도를 계산한다.
