Braid Public-Key Cryptosystem

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


Published : Crypto 2000

Abstract :
 The braid groups are infinite non-commutative groups naturally arising from geometric braids. The braid groups can serve as a good source to enrich cryptography. The feature that makes the braid groups useful to cryptography includes the followings: (i) The word problem is solved via a fast algorithm which computes the canonical form which can be efficiently manipulated by computers. (ii) The group operations can be performed efficiently. (iii) The braid groups have many mathematically hard problems that can be utilized to design cryptographic primitives. The efficiency of our systems is demonstrated by their speed and information rate. Our public key encryption sheme is provably secure. The foundation of our systems is quite different from widely used cryptosystems based on number theory, but there are some similarities in design.

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

Scheme :

  • Key generation : Choose randomly x in B2n and a in UBn . G : hash function.
      Public key : pk=(x,a-1xa)  Private key : sk=a
  • Encryption : For a given plaintext m, choose randomly r in LBn .
    Epk(m,r)=(r-1xr, G(r-1a-1xar)+m)
  • Decryption : For a ciphertext (c,d), compute
    Dsk(c,d)=G(a-1ca)+d

    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.