Braid Public-Key Cryptosystem
Published : Crypto 2000
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
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 .
Decryption : For a ciphertext (c,d), compute
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),
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
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.