Advertisement

A Practical Attack on Some Braid Group Based Cryptographic Primitives

  • Dennis Hofheinz
  • Rainer Steinwandt
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2567)

Abstract

A simple heuristic approach to the conjugacy problem in braid groups is described. Although it does not provide a general solution to the latter problem, it demonstrates that various proposed key parameters for braid group based cryptographic primitives do not offer acceptable cryptographic security. We give experimental evidence that it is often feasible to reveal the secret data by means of a normal PC within a few minutes.

Keywords

braid groups cryptanalysis 

References

  1. [AAFG01]
    Iris Anshel, Michael Anshel, Benji Fisher, and Dorian Goldfeld. New Key Agreement Protocols in Braid Group Cryptography. In David Naccache, editor, “Topics in Cryptology — CT-RSA 2001”, volume 2020 of Lecture Notes in Computer Science, pages 13–27. Springer, 2001. 187, 188, 190, 193, 194, 195, 196CrossRefGoogle Scholar
  2. [AAG99]
    Iris Anshel, Michael Anshel, and Dorian Goldfeld. An Algebraic Method for Public-Key Cryptography. Mathematical Research Letters, 6:287–291, 1999. 187, 188, 194zbMATHMathSciNetGoogle Scholar
  3. [Art25]
    Emil Artin. Theorie der Zöpfe. Hamb. Abh., 4:47–72, 1925. 188zbMATHCrossRefGoogle Scholar
  4. [Bir74]
    Joan S. Birman. Braids, Links, And Mapping Class Groups. Number 82 in Annals of Mathematics Studies. Princeton University Press and University of Tokyo Press, Princeton, New Jersey, 1974. 187Google Scholar
  5. [BKL98]
    Joan S. Birman, Ki Hyoung Ko, and Sang Jin Lee. A new approach to the word and conjugacy problems in the braid groups. Advances in Mathematics, 139:322–353, 1998. 190zbMATHCrossRefMathSciNetGoogle Scholar
  6. [Cha01]
    Jae Choon Cha. CBraid: a C++ library for computations in braid groups, 2001. At the time of writing available electronically at http://knot.kaist.ac.kr/~jccha/cbraid/. 193
  7. [CKL+01]
    Jae Choon Cha, Ki Hyoung Ko, Sang Jin Lee, Jae Woo Han, and Jung Hee Cheon. An Efficient Implementation of Braid Groups. In Colin Boyd, editor, Advances in Cryptology — ASIACRYPT 2001, volume 2248 of Lecture Notes in Computer Science, pages 144–156. Springer, 2001. 189, 196Google Scholar
  8. [EM94]
    Elsayed A. Elrifai and H.R. Morton. Algorithms for positive braids. Quarterly Journal of Mathematics Oxford, 45:479–497, 1994. 188, 189zbMATHCrossRefMathSciNetGoogle Scholar
  9. [Gar69]
    F.A. Garside. The Braid Group and Other Groups. Quarterly Journal of Mathematics Oxford, 20:235–254, 1969. 187, 188, 189zbMATHCrossRefMathSciNetGoogle Scholar
  10. [GZ91]
    Max Garzon and Yechezkel Zalcstein. The Complexity of Grigorchuk groups with application to cryptography. Theoretical Computer Science, 88:83–98, 1991. 187zbMATHCrossRefMathSciNetGoogle Scholar
  11. [Hug02]
    Jim Hughes. A Linear Algebraic Attack on the AAFG1 Braid Group Cryptosystem. In Lynn Batten and Jennifer Seberry, editors, Information Security and Privacy. 7th Australasian Conference, ACISP 2002, volume 2384 of Lecture Notes in Computer Science, pages 176–189. Springer, 2002. 187, 195Google Scholar
  12. [KLC+00]
    Ki Hyoung Ko, Sang Jin Lee, Jung Hee Cheon, Jae Woo Han, Ju sung Kang, and Choonsik Park. New Public-Key Cryptosystem Using Braid Groups. In Mihir Bellare, editor, Advances in Cryptology — CRYPTO 2000, volume 1880 of Lecture Notes in Computer Science, pages 166–183. Springer, 2000. 187, 188, 190, 193, 195, 196Google Scholar
  13. [LL02]
    Sang Jin Lee and Eonkyung Lee. Potential Weaknesses of the Commutator Key Agreement Protocol Based On Braid Groups. In Lars Knudsen, editor, Advances in Cryptology–EUROCRYPT 2002, volume 2332 of Lecture Notes in Computer Science, pages 14–28. Springer, 2002. 187, 189, 192, 194Google Scholar
  14. [Wag90]
    Neal R. Wagner. Searching for Public-Key Cryptosystems. In Proceedings of the 1984 Symposium on Security and Privacy (SSP’ 84), pages 91–98, Los Angeles, Ca., USA, 1990. IEEE Computer Society Press. 187Google Scholar
  15. [WM85]
    Neal R. Wagner and Marianne R. Magyarik. A Public Key Cryptosystem Based on the Word Problem. In G.R. Blakley and D. Chaum, editor, Advances in Cryptology. Proceedings of CRYPTO 1984, volume 196 of Lecture Notes in Computer Science, pages 19–36. Springer, 1985. 187Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Dennis Hofheinz
    • 1
  • Rainer Steinwandt
    • 1
  1. 1.IAKS, Arbeitsgruppe Systemsicherheit, Prof. Dr. Th. Beth Fakultät für InformatikUniversität KarlsruheKarlsruheGermany

Personalised recommendations