Braid group cryptography. (English) Zbl 1203.94100
Berrick, A. Jon (ed.) et al., Braids. Introductory lectures on braids, configurations and their applications. Based on the program “Braids”, IMS, Singapore, May 14–July 13, 2007. Hackensack, NJ: World Scientific (ISBN 978-981-4291-40-8/hbk). Lecture Notes Series. Institute for Mathematical Sciences. National University of Singapore 19, 329-403 (2010).
This paper gives a broad survey of recent and very recent developments in the area of cryptography by means of new technics and ideas. In order to give the reader an impression on the content of the paper, I mention the chapters with its subsections. We have
1) Introduction; 2) The Braid Group (Basic definitions, algebraic and geometrical), (The Birman-Ko-Lee’s presentation); 3) Normal forms of elements in the Braid Group (Garside’s NOrmal Form and the Birman-Ko-Lee canonical form); 4) Algorithms for solving the word problem in Braid Group (Dehornoy’s handles reduction etc.); 5) What is Public-Key-Cryptography (Diffie-Hellman, RSA); 6) First cryptosystems based on Braid Groups (Problems, Key-exchange protocols, like Anohel-Anshel-Goldfeld, Diffie-Hellman, encryption/decryption, authentication schemes); 7) Attacks on the Conjugacy Search Problem using Summit sets (29 page); 8) More Attacks on the Conjugacy Search Problem (length based attacks, Hughes/Tannenbaum, memory approach, Myasinkov/Ushakov, linear representations like Burau, Lawrence/Krammer); 9) Newly suggested Braid Group Cryptosystems, their imploy analyses and their formal applications (algebraic eraser, combinatorial group theory) (12 pages); 10) and 11) Future directions (the Thompson group, Shpilrain/Ushakov, length-based attack, the Membership Problem, polycyclic groups, Miller groups, Grigorchuk groups).
There are 133 reference papers.
This paper is a very valuable game, workwhile to be studied over and over.
For the entire collection see [Zbl 1186.20001].
1) Introduction; 2) The Braid Group (Basic definitions, algebraic and geometrical), (The Birman-Ko-Lee’s presentation); 3) Normal forms of elements in the Braid Group (Garside’s NOrmal Form and the Birman-Ko-Lee canonical form); 4) Algorithms for solving the word problem in Braid Group (Dehornoy’s handles reduction etc.); 5) What is Public-Key-Cryptography (Diffie-Hellman, RSA); 6) First cryptosystems based on Braid Groups (Problems, Key-exchange protocols, like Anohel-Anshel-Goldfeld, Diffie-Hellman, encryption/decryption, authentication schemes); 7) Attacks on the Conjugacy Search Problem using Summit sets (29 page); 8) More Attacks on the Conjugacy Search Problem (length based attacks, Hughes/Tannenbaum, memory approach, Myasinkov/Ushakov, linear representations like Burau, Lawrence/Krammer); 9) Newly suggested Braid Group Cryptosystems, their imploy analyses and their formal applications (algebraic eraser, combinatorial group theory) (12 pages); 10) and 11) Future directions (the Thompson group, Shpilrain/Ushakov, length-based attack, the Membership Problem, polycyclic groups, Miller groups, Grigorchuk groups).
There are 133 reference papers.
This paper is a very valuable game, workwhile to be studied over and over.
For the entire collection see [Zbl 1186.20001].
Reviewer: R. W. van der Waall (Huizen)
MSC:
| 94A60 | Cryptography |
| 94A62 | Authentication, digital signatures and secret sharing |
| 20F36 | Braid groups; Artin groups |
| 20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |
