Cryptanalysis on braid cryptosystem via the Krammer representation = 크래머 재표현을 통한 땋임암호체계의 분석

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 299
  • Download : 0
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.
Advisors
Ko, Ki-Hyoungresearcher고기형researcher
Description
한국과학기술원 : 수학전공,
Publisher
한국과학기술원
Issue Date
2003
Identifier
180021/325007 / 020013327
Language
eng
Description

학위논문(석사) - 한국과학기술원 : 수학전공, 2003.2, [ vi, 28 p. ]

Keywords

braidcryptosystem; Krammer representation; 크래머재표현; 땋임암호

URI
http://hdl.handle.net/10203/42056
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=180021&flag=dissertation
Appears in Collection
MA-Theses_Master(석사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0