[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Towards generating secure keys for braid cryptography

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

Braid cryptosystem was proposed in CRYPTO 2000 as an alternate public-key cryptosystem. The security of this system is based upon the conjugacy problem in braid groups. Since then, there have been several attempts to break the braid cryptosystem by solving the conjugacy problem in braid groups. In this article, we first survey all the major attacks on the braid cryptosystem and conclude that the attacks were successful because the current ways of random key generation almost always result in weaker instances of the conjugacy problem. We then propose several alternate ways of generating hard instances of the conjugacy problem for use braid cryptography.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Anshel I., Anshel M. and Goldfeld D. (1999). An algebraic method for public-key cryptography. Math. Res. Lett. 6: 287–291

    MATH  MathSciNet  Google Scholar 

  2. Birman J.S.: Braids, links and mapping class groups, Annals of Math. Study 82, Princeton University Press (1974).

  3. Birman J.S., Gebhardt V., González-Mensese J.: Conjugacy in Garside groups I: Cyclings, Powers, and Rigidity, arXiv:math.GT/0605230

  4. Birman J.S., Ko K.H. and Lee S.J. (2001). The infimum, supremum, and geodesic length of a braid conjugcy class. Adv. Math. 164(1): 41–56

    Article  MATH  MathSciNet  Google Scholar 

  5. Cha J.C., Ko K.H., Lee S.J., Han J.W., Cheon J.H.: An efficient implementation of braid groups. Advances in Cryptology: Proceedings of ASIACRYPT 2001, Lecture Notes in Computer Science, Springer-Verlag, vol 2248 pp. 144–156 Springer-verlag (2001).

  6. Cheon J.H., Jun B.: A polynomial time algorithm for the braid Diffie-Hellman conjugacy problem. Advances in Cryptology: Proceedings of CRYPTO 2003, Lecture Notes in Computer Science, vol 2729, pp. 212–225. Springer-Verlag-2003.

  7. Dehornoy P. (2004). Braid-based cryptography. Contemp. Math. 360: 5–33

    MathSciNet  Google Scholar 

  8. El-Rifai E.A and Morton H.R. (1994). Algorithms for positive braids. Quart. J. Math. Oxford Ser. 45(2): 479–497

    Article  MathSciNet  Google Scholar 

  9. Franco N. and Gonazález-Meneses J. (2003). Conjugacy problem for braid groups and Garside groups. J. Algebra 266(1): 112–132

    Article  MATH  MathSciNet  Google Scholar 

  10. Garber D., Kaplan S., Teicher M., Tsaban B., Vishne U.: Length-based conjugacy search in the Braid groups. http://arXiv.org/abs/math.GR/0209267

  11. Garside F.A. (1969). The braid group and other groups. Quart. J. Math. Oxford Ser. 20(2): 235–254

    Article  MATH  MathSciNet  Google Scholar 

  12. Gebhardt V.: A new approach to the conjugacy problem in Garside groups, to appear in J. Algebra, (2005).

  13. Gebhardt V. (2006). Conjugacy search in braid groups, from a braid-based cryptography point of view, applicable algebra in engineering. commun computi. 17(3–4): 219–238

    MATH  MathSciNet  Google Scholar 

  14. Hofheinz D., Steinwandt R.: A practical attack on some braid group based cryptographic primitives, 6th International Workshop on Practice and Theory in Public Key Cryptography: Proceedings of PKC 2003, Lecture Notes in Computer Science, vol 2567, pp. 187–198. Springer Verlag (2002).

  15. Hughes J.: A linear algebraic attack on the AAFG1 braid group cryptosystem, ACISP 2002, Lecture Notes in Computer Science, vol 2384, pp. 176–189. Springer-Verlag (2002).

  16. Hughes J., Tannenbaum A.: Length-based attacks for certain group based encryption rewriting systems, Workshop SECI02, Sécurité de la Communication sur Internet, Sept. 2002.

  17. Ko K.H., Choi D.H., Cho M.S., Lee J.W.: New signature scheme using conjugacy problem, Available at: http://eprint.iacr.org/2002/168.pdf

  18. Ko K.H., Lee J.W.: A fast algorithm to the conjugacy problem on generic braids, to appear in the proceedings of Knot theory for Scientific Objects, March, 2006, Osaka, Japan.

  19. Ko K.H., Lee J.W.: A polynomial-time solution to the reducibility problem, arXiv:math.GT/0610746.

  20. Ko K.H., Lee S.J., Cheon J.H., Han J.W., Kang J.S., Park C.S.: New public-key cryptosystem using braid groups. Advances in Cryptology: Proceedings of CRYPTO 2000. Lecture Notes in Computer Science, vol 1880, pp. 166–183. Springer-Verlag (2000).

  21. Lee E. (2004). Braid groups in cryptology. IEICE Trans. Fundamentals, E 87A(5): 986–992

    Google Scholar 

  22. Lee S.J.: Algorithmic solutions to decision problems in the braid groups, PhD Thesis, Korea Advanced Institute of Science and Technology (2000).

  23. Lee S.J., Lee E.K.: Potential weakness of the commutator key agreement protocol based on braid groups, Proceedings of EUROCRYPT 2002, Lecture Notes in Computer Science, vol 2332, pp. 14–28. Springer-Verlag (2002).

  24. Lee E., Park J.H.: Cryptanalysis of the public-key encryption based on braid groups, Advances in Cryptology: Proceedings of EUROCRYPT 2003, Lecture Notes in Computer Science, vol 2565, pp. 477–490. Springer-Verlag (2003).

  25. Maffre S. (2006). A weak key test for braid based cryptography. Designs Code. Cryptogr. 39(3): 347–373

    Article  MATH  MathSciNet  Google Scholar 

  26. Myasnikov A., Shpilrain V., Ushakov A.: A practical heuristic attack on the Ko-Lee key exchange protocol. Advances in Cryptology: Proceedings of CRYPTO 2005, Lecture Notes in Computer Science, vol 3621, pp. 86–96. Springer-Verlag (2005).

  27. Sibert H.: Algorithmique des tresses, PhD Thesis, Universite de Caen (2003).

  28. Sibert H., Dehornoy P. and Girault M. (2006). Entity authentication schemes using braid word reduction. Discrete Applied Math. 154(2): 420–436

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Korea Advanced Institute of Science and Technology, Daejeon, 305-701, Korea

    Ki Hyoung Ko, Jang Won Lee & Tony Thomas

Authors
  1. Ki Hyoung Ko
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jang Won Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tony Thomas
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ki Hyoung Ko.

Additional information

Communicated by P. Wild.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ko, K.H., Lee, J.W. & Thomas, T. Towards generating secure keys for braid cryptography. Des. Codes Cryptogr. 45, 317–333 (2007). https://doi.org/10.1007/s10623-007-9123-0

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-007-9123-0

Keywords

AMS Classifications

Search

Navigation