Cryptography and Braid Groups

Braid Groups: Intro
- Braid Group (@Eric Weisstein's World of Mathematics)
- Braids (intro by Stephen Bigelow)
- Minicourse: Conjugacy problem in braid groups and applications (Ki Hyoung Ko (KAIST) and Sang Jin Lee (KIAS))
Braid Group Cryptography: Intro
- The Arithmetica Key Exchange (Michael Anshel)
- Making, Breaking Codes: An Introduction to Cryptology (Book by Paul Garrett, contains a section on braid group cryptography)
- Special Session for Braid Cryptosystems (PKC 2001 Tutorial)
- Arithmetica Key Agreement Protocol (Jim Hughes, Eurocrypt 2000 rump session)
- Braid group cryptography untangled (Andrew Bolstad)
- An Overview of Braid Group Cryptography (Karl Mahlburg)
- Braid Group Cryptography (David Garbner, survey, 2007)
Papers: Braid Groups
- On the image of the Lawrence-Krammer representation (Ryan Budney)
- The Lawrence--Krammer representation is unitary (Won Taek Song)
- Braids and Permutations (Vladimir Lin, math.GR/0404528)
- Geometric presentations for Thompson's groups (Patrick Dehornoy, math.GR/0407096)
- The group of parenthesized braids (Patrick Dehornoy, math.GR/0407097)
- Braids: A Survey (Joan S. Birman, Tara E. Brendle (math.GT/0409205, submitted to Handbook of Knot Theory))
- Unprovability results involving braids (Lorenzo Carlucci, Patrick Dehornoy, Andreas Weiermann, 2007)
Papers: Braid Group Algorithms
- Word Problem
  - A new approach to the word and conjugacy problems in the braid groups (Birman, Ko, Lee, 1998)
    - Updated version
      (math.GT/9712211)
  - A New Algorithm for Solving the Word Problem in Braid Groups (David Garber, Shmuel Kaplan, Mina Teicher, math.AG/0101053, 2001)
- The infimum, supremum and geodesic length of a braid conjugacy class (Joan S. Birman, Ki Hyoung Ko, Sang Jin Lee, math.GT/0003125)
- The generalized conjugacy search problem and the Burau representation (S.G.Hahn, E.K.Lee, Je Hong Park, prepreprint, 2000)
- Identifying Half-Twists Using Randomized Algorithm Methods (S. Kaplan, M. Teicher, math.AG/0106007 (last revised on 08.10.02))
- Faithful Linear Representations of the Braid Groups (Vladimir Turaev, math.GT/0006202)
- Conjugacy problem for braid groups and Garside groups (N. Franco, J. Gonzalez-Meneses, math.GT/0112310)
- Computation of Centralizers in Braid groups and Garside Groups (Nuno Franco, Juan Gonzalez-Meneses, math.GT/0201243)
- The Lawrence--Krammer representation is unitary (Won Taek Song)
- Average-case complexity and decision problems in group theory (Ilya Kapovich, Alexei Myasnikov, Paul Schupp, Vladimir Shpilrain)
- An algorithm for the word problem in braid groups (Bert Wiest, math.GT/0211169)
- Identifying Powers of Half-Twists and Computing its Root (T. Ben-Itzhak, S. Kaplan, M. Teicher, math.AG/0211197)
- Computation of Centralizers in Braid groups and Garside Groups (Nuno Franco, Juan Gonzalez-Meneses, math.GT/0201243)
- Improving an algorithm to solve Multiple Simultaneous Conjugacy Problems in braid groups (Juan Gonzalez-Meneses, math.GT/0212150)
- Conjugacy in Artin groups and applications to the classification of surfaces (Eddy Godelle, Mina Teicher, Shmuel Kaplan, math.GR/0312188)
- Probabilistic Solutions of Equations in the Braid Group (D. Garber, S. Kaplan, M. Teicher, B. Tsaban, U. Vishne, math.GR/0404076)
- Braids and Permutations (Vladimir Lin, math.GR/0404528)
- Conjugacy problem for subgroups with applications to Artin groups and braid type groups (Nuno Franco, math.GR/0411322)
- The conjugacy search problem in public key cryptography: unnecessary and insufficient (Vladimir Shpilrain and Alexander Ushakov, eprint 2004/321)
- Braid Compression (Martin Hock, 2004)
Papers: Cryptography
- 1999
  - Constructing Public Key Cryptosystems via Combinatorial Group Theory (Michael Anshel, 1999)
  - An Algebraic Method for Public-Key Cryptography (Iris Anshel, Michael Anshel, Dorian Goldfeld, Mathematical Research Letters {6} (1999) 287--291)
    - Alternative download
  - A New Group Theoretic Protocol for Key Exchange (Iris Anshel, Michael Anshel, Dorian Goldfeld, 1999)
- 2000
  - New Public-key Cryptosystem using Braid Groups (Ki Hyoung Ko, Sang Jin Lee, Jung Hee Cheon, Jae Woo Han, Ju-sung Kang, Choonsik Park, Crypto 2000)
- 2001
  - New Key Agreement Protocols in Braid Group Cryptography (Iris Anshel, Michael Anshel, Benji Fisher, Dorian Goldfeld, RSA 2001)
  - The hidden bit in the generalized conjugacy search problem in braid groups (S.G.Hahn, Eonkyung K. Lee, submitted, 2001)
  - Pseudorandomness from Braid groups (Eonkyung K.Lee, S.J.Lee, S.G.Hahn, CRYPTO 2001)
- 2002
  - Length-based attacks for certain group based encryption rewriting systems (J. Hughes, A. Tannenbaum, 2000 (Published in SECI 02))
  - Towards a Uniform Description of Several Group Based Cryptographic Primitives (Maria Isabel Gonzalez Vasco, Consuelo Martinez, Rainer Steinwandt (eprint 2002/048))
  - A Linear Algebraic Attack on the AAFG1 Braid Group Cryptosystem (Jim Hughes, ACISP 2002)
  - Potential Weaknesses of the Commutator Key Agreement Protocol Based on Braid Groups (Sang Jin Lee, Eonkyung Lee, EUROCRYPT 2002)
  - Reaction Attacks on Public Key Cryptosystems Based on the Word Problem (Maria Isabel Gonzalez Vasco and Rainer Steinwandt, eprint 2002/139)
  - Length-based conjugacy search in the Braid group (D. Garber, S. Kaplan, M. Teicher, B. Tsaban, U. Vishne, math.GR/0209267)
  - A Practical Attack on Some Braid Group Based Cryptographic Primitives (Dennis Hofheinz and Rainer Steinwandt, PKC 2003)
  - Public-key cryptography and invariant theory (D. Grigoriev, cs.CR/0207080)
  - New Signature Scheme Using Conjugacy Problem (Ki Hyoung Ko and Doo Ho Choi and Mi Sung Cho and Jang Won Lee, eprint 2002/168)
  - Entity Authentication Schemes Using Braid Word Reduction (Hervé SIBERT and Patrick DEHORNOY and Marc GIRAULT, eprint 2002/187)
  - [scholar]Non-abelian key agreement protocols (Iris Anshel, Michael Anshel and Dorian Goldfeld, Discrete Applied Mathematics 2002)
- 2003
  - Homomorphic public-key cryptosystems and encrypting boolean circuits (Dima Grigoriev, Ilia Ponomarenko, cs.CR/0301022)
  - An Authenticated Group Key Agreement Protocol on Braid groups (Ho-Kyu Lee, Hyang-Sook Lee, Young-Ran Lee, eprint 2003/018)
  - A Polynomial Time Algorithm for the Braid Diffie-Hellman Conjugacy Problem (Jung Hee Cheon and Byungheup Jun, eprint 2003/019)
  - Cryptanalysis of the Public-key Encryption based on Braid Groups (Eonkyung Lee, Je Hong Park, Eurocrypt 2003)
  - Algorithms in Braid Groups (Matthew J. Campagna, eprint 2003/099)
  - A New Approach to the Conjugacy Problem in Garside Groups (Volker Gebhardt, math.GT/0306199)
  - Assessing security of some group based cryptosystems (Vladimir Shpilrain, eprint 2003/123)
  - Braid-based cryptography (Partrick Dehornoy, preprint (2003))
  - Braid Group Cryptography and Quantum Cryptoanalysis (Michael Anshel)
  - [scholar]Non-abelian key agreement protocols (Anshel, Iris; Anshel, Michael; Goldfeld, Dorian; Discrete Appl. Math. 130, No.1, 3-12 (2003)) Milton Chowdhury, "An Algebraic Key Establishment Protocol", 06-Dec-2003, MPS%3a Applied mathematics/0312006 [ResearchIndex]
    Milton Chowdhury, "An Algebraic Key Establishment Protocol With A Group Theoretic Illustration-The Braid PKC With Greatest Security", 10-Dec-2003, MPS%3a Applied mathematics/0312011 [ResearchIndex]
    Milton Chowdhury, "A Generalisation Of the KLCHKP Public Key Cryptosystem and a New Public Key Cryptosystem Based On the Decomposition Problem", 02-Dec-2003, MPS%3a Applied mathematics/0312004 [ResearchIndex]
    Volker Gebhardt, "A New Approach to the Conjugacy Problem in Garside Groups", 11-Jun-2003, MPS%3a Pure mathematics/0306019 [ResearchIndex]
    Milton Chowdhury, "Solution Of the Generalised Word Problem For Various Subgroups Of the Braid Group and a Solution of the Conjugacy Problem in the Braid Group", 26-Dec-2003, MPS%3a Pure mathematics/0312031 [ResearchIndex]
    Milton Chowdhury, "New Key Establishment Protocol Based On the Decomposition Problem", 01-Dec-2003, MPS%3a Applied mathematics/0312003 [ResearchIndex]
- 2004
  - Provably-Secure Identification Scheme based on Braid Group (Zeen Kim, Kwangjo Kim, SCIS 2004)
  - Combinatorial group theory and public key cryptography (Vladimir Shpilrain and Gabriel Zapata, eprint 2004/242)
  - The conjugacy search problem in public key cryptography: unnecessary and insufficient (Vladimir Shpilrain and Alexander Ushakov)
- 2005
  - A Practical Attack on the Root Problem in Braid Groups (Anja Groch and Dennis Hofheinz and Rainer Steinwandt, eprint 2005/459)
- Towards Generating Secure Keys for Braid Cryptography (Ki Hyoung Ko and Jang Won Lee and Tony Thomas, eprint 2007/149)
- Cryptanalysis of Anshel-Anshel-Goldfeld-Lemieux key agreement protocol (Alex D. Myasnikov, Alexander Ushakov, 2008)
Papers: related groups etc
- Conjugacy of finite subsets in hyperbolic groups (Martin R. Bridson and James Howie)
- Homomorphic public-key cryptosystems over groups and rings (Dima Grigoriev, Ilia Ponomarenko, cs.CR/0309010)
- Polycyclic groups: A new platform for cryptology? (Bettina Eick, Delaram Kahrobaei, math.GR/0411077)
- Conjugacy of finite subsets in hyperbolic groups (Martin R. Bridson, James Howie)
Presentations
- The LeftSSS attack on Ko-Lee-Cheon-Han-Kang-Park Key Agreement Protocol in B₄₅ (Jim Hughes, rump session of Crypto 2000)
- A Linear Time Matrix Key Agreement Protocol (Dorian Goldfeld, CRY2002)
- - Slides
Seminars
- St Andrews PolyCyclic Groups and Cryptologic Applications Seminar
Implementations
- Practical comparison of Fast Public-key Cryptosystems (Priit Karu, Jonne Loikkanen, 2000)
- An Efficient Implementation of Braid Groups (J. Cha, K. Koh, S. Lee, J. Han, and J. Cheon, Asiacrypt 2001)
Paper farms
- Papers (crypto@kaist)
People working on braid group cryptography
- Michael Anshel (CUNY)
- Jung Hee Cheon (Korea.Seoul NU)
- Dorian Goldfeld (Columbia)
- Sang Geun Hahn (KAIST)
- Juan Gonzalez-Meneses (Seville)
- Dennis Hofheinz (Karlsruhe)
- Ki Hyoung Ko (KAIST)
- Jim Hughes (StorageTek)
- Eonkyung Lee (Sojang University)
- Sang Jin Lee (KAIST)
- Rainer Steinwandt (USA.FAU)
Some more people working on braid groups
- Stephen Bigelow (USA.UCSB)
- Nigel Boston (USA.WISC)
- Ryan Budney (Cornell)
- Joan Birman (Columbia)
- Patrick Dehornoy (Caen)
- Shmuel Kaplan (Bar-Ilan)
- Mina Teicher (Bar-Ilan)
- Matthieu Picantin (Caen)
Companies
- Arithmetica
Software
- The Magnus combinatorial group theory software project
- Asphalis ("Asphalis is a new Public Key Infrastructure based on braid groups protocol")
- KnotTTY (Remote secure shell using braids)
Patents
- [scholar]Method and apparatus for cryptographically secure algebraic key establishment protocols based on monoids (United States Patent 6,493,449, Anshel , et al., December 10, 2002)
- Public key cryptographic method based on braid groups (Marc Girault, Herve Sibert, Patrick Dehornoy, Jean-Francois Misarsky, US Patent 2004240672)
- Cryptosystems using commuting pairs in a monoid (US Patent 7,136,484, Koh; Jee H.)

Cryptology Pointers by Helger Lipmaa
Got any suggestions or additional links? Mail to <helger.lipmaa>gmail.com
NB! If you find any broken links, please be kind and report them to me together with their current location!

(C) Helger Lipmaa 1997-2009.