• Tutorial Overview
• Introduction to Cryptography
• Introduction to Braids
• Properties of Braids
• Protocols
• Example Of Key Exchange
• Example Of Key Exchange (with pictures)
• Security and Attacks
• Further reading

Further reading

Summary of relevant papers:

• In "An Efficient Implementation of Braid Groups" various algorithms used in braid group cryptography are implemented in order to test the efficiency.
• In "A Practical Attack on Some Braid Group Based
  Cryptographic Primitives"  they claim they have a heuristic-based approach to solving the conjugacy problem, which does not produce a solution in general, but it demonstrates that various proposed key parameters for braid group based cryptographic primitives do not offer acceptable cryptographic security.
• In "THE CONJUGACY SEARCH PROBLEM IN PUBLIC KEY
  CRYPTOGRAPHY: UNNECESSARY AND INSUFFICIENT"  they claim that in the Ko et al version, a weaker problem than the conjugacy search problem can be solved to gain access to the secret key, whereas in the Anshel at al version, solving the conjugacy search problem is not sufficient to get the secret key.
• "AN OVERVIEW OF BRAID GROUP CRYPTOGRAPHY" is a recent, expository paper which discusses the specifications, attacks, and responses of both the Anshel, Anshel, and Goldfeld Commutator and the Cho et al. Diffie-Hellman Conjugacy key exchange protocols.
• "AN ALGEBRAIC METHOD FOR PUBLIC-KEY CRYPTOGRAPHY" by Anshel et al. is a short article about the use of algebraic structures used in protocols.
• "A New Algorithm for Solving the Word Problem in Braid Groups" provides an alternative solution to the word problem, based on diffeomorphisms of the punctured disk. They claim that it their algorithm is faster, in comparison with known algorithms, for short braid words with respect to the number of generators combining the braid, and it is almost independent of the number of strings in the braids.
• In "Length-Based Attacks for Certain Group Based Encryption Rewriting Systems" they describe a probabilistic attack of cryptosystems based on the word/conjugacy problems; the attack is a "length attack" - based on having a canonical representative of each string relative to which a length function may be computed.
•  Slides from four talks from a special session for braid cryptosystems in Korei, at PKC 2001:
  (i)   Braid cryptosystems. Apparently it is an improved version (comparing to the Crypto 2000 version) of  the key exchange scheme and the public key cryptosystem using braid groups.
  (ii)     Implementations of the braid cryptosystems.
  (iii)    Mathematical background on braids.
  (iv)    An overview of new public key cryptosystems.
• "A Linear Algebraic Attack on the AAFG1 Braid Group Cryptosystem" using the Burau matrix representation and computational linear algebra to show certain class of keys in the Anshel protocol are weak.
• In "Braid Compression" a method for shortening braid descriptions is given.
• "Provably-Secure Identification Scheme based on Braid Group"  in SCIS 2004 gives a new interactive identification scheme based on the conjugacy problem (they prove something about security against passive attacks).
• PROBABILISTIC SOLUTIONS OF EQUATIONS IN THE BRAID GROUP provides more attacks on the braid group protocols.
• The main ideas in this tutorial are based on New Public-key Cryptosystem using Braid Groups by Ki Hyoung Ko, Sang Jin Lee, Jung Hee Cheon, Jae Woo Han, Ju-sung Kang, Choonsik Park, Crypto 2000.

Useful sites:

• Cryptology pointers by Helger Lipmaa seems to contain links to everywhere you are likely to need! His site on braid groups and cryptography may be handy.
• The Home of Braid Cryptography from the Knot Theory and Cryptography Research Group at the Korea Advanced Institute of Science and Technology- one can download tutorials on braid cryptography (PKC 2001), implementation paper (Asiscrypt 2001) and the original paper on New PKC using braid groups (Crypto 2000) from here.
• Softpanorama Slightly Skeptical Crypto Algorithms Links provides links to many areas of cryptography in general.
• Michael Anshel's homepage has links to many areas of Computer Science including Security & Cryptography.
• Cryptome provides many interesting stories involving supposedly decrypted information.
• PKC  (public key cryptography) conferences list.

The main material on the protocols etc has been adapted (hopefully explained in even simpler terms) from various sources; most notably the original papers on Braid Group Cryptosystems by Ko et al. Please feel free to email me at: Andrew -dot- fish -at- brighton -dot- ac -dot- uk if you wish to comment on anything.  

This tutorial was produced in collaboration with Ebru Keyman, and hopefully we will make further extensions to it soon. Please feel free to provide any suggestions for related topics that would be useful.  

Previous