Braid Key Agreement Scheme

[HOME] [knot.kaist.ac.kr]


Published : Crypto 2000

Underlying Problems : Generalized Conjugacy Problem, Computational Diffie-Hellman type Problem on Braid Groups

Scheme :
(1) Alice chooses randomly x in B2n, a in UBn and sends (x,a-1xa) to Bob.
(2) Bob chooses randomly b in LBn and sends b-1xb to Alice.
(3) Alice and Bob share a-1b-1xba=b-1a-1xab.

References :

  • E. Aritn, Theory of braids, Annals of Math. 48 (1947), 101-126.
  • J. S. Birman, Braids, links and mapping class groups, Annals of Math. Study no 82, Princeton University Press (1974).
  • J. S. Birman, K. H. Ko and S. J. Lee, A new approach to the word and conjugacy problems in the braid groups, Advances in Math. 139 (1998), 322-353.
  • W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Transactions on Information Theory 22 (1976), 644-654.
  • E. A. Elrifai and H. R. Morton, Algorithms for positive braids, Quart. J. Math. Oxford 45 no. 2 (1994), 479-497.
  • D. Epstein and J. Cannon, D. Holt, S. Levy, M. Paterson and W. Thurston, Word processing in groups, Jones & Bartlett, (1992).
  • R. Fenn, D. Rolfsen and J. Zhu, Centralisers in the braid group and singular braid monoid, Enseign. Math. (2) 42 no. 1-2 (1996), 75-96.
  • F. A. Garside, The braid group and other groups, Quart. J. Math. Oxford 20 no. 78 (1969), 235-254.
  • E. S. Kang, K. H. Ko and S. J. Lee, Band=generator presentation for the 4-braid group, Topology Appl. 78 (1997), 39-60.
  • K. H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J. Kang and C. Park, New Public-Key Cryptosystem Using Braid Groups, Proceedings of Crypto 2000, LNCS 1880 (2000),166-183.
  • J. C. Cha, K. H. Ko, S. J. Lee, J. W. Han and J. H. Cheon, An Efficient Implementation of Braid Groups, Proceedings of Asiacrypt 2001, LNCS 2248 (2001), 144-156.
  • E. Lee, S. J. Lee and S. G. Hahn, Pseudorandomness from Braid Groups, Proceedings of Crypto 2001, LNCS 2139 (2001), 486-502.