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
- "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
- 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.
- Cryptology pointers by
Helger Lipmaa seems to contain links to everywhere you are likely to need! His site on
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
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 &
- 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.