nLab braid group cryptography -- references

Braid group cryptography

Partly motivated by the possibility of quantum computation eventually breaking the security of cryptography based on abelian groups, such as elliptic curves, there are proposals to use non-abelian braid groups for purposes of cryptography (“post-quantum cryptography”).

Via Conjugacy Search

An early proposal was to use the Conjugacy Search Problem in braid groups as a computationally hard problem for cryptography. This approach, though, was eventually found not to be viable.

Original articles:

• Iris Anshel, M. Anshel and D. Goldfeld, An algebraic method for public-keycryptography, Math. Research Letters 6 (1999), 287–291 (pdf)

• K.H. Ko, S.J. Lee, J.H. Cheon , J.W. Han, J. Kang, C. Park , New Public-Key Cryptosystem Using Braid Groups, In: M. Bellare (ed.) Advances in Cryptology — CRYPTO 2000 Lecture Notes in Computer Science, vol 1880. Springer 2000 (doi:10.1007/3-540-44598-6_10)

Review:

• Karl Mahlburg, An Overview of Braid Group Encryption, 2004 (pdf)

• Parvez Anandam, Introduction to Braid Group Cryptography, 2006 (pdf)

• David Garber, Braid Group Cryptography, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore (arXiv:0711.3941, doi:10.1142/9789814291415_0006)

• Cryptowiki, Cryptosystems based on braid groups

Via E-multiplication

A followup proposal was to use the problem of reversing E-multiplication in braid groups, thought to remedy the previous problems.

Original article:

• Iris Anshel, Derek Atkins, Dorian Goldfeld and Paul E Gunnells, WalnutDSA(TM): A Quantum-Resistant Digital Signature Algorithm (eprint:2017/058)

Review:

• Magnus Ringerud, WalnutDSA: Another attempt at braidgroup cryptography, 2019 (pdf)

But other problems were found with this approach, rendering it non-viable.

Original article:

• Matvei Kotov, Anton Menshov, Alexander Ushakov, An attack on the Walnut digital signature algorithm, Designs, Codes and Cryptography volume 87, pages 2231–2250 (2019) (doi:10.1007/s10623-019-00615-y)

Review:

• José Ignacio Escribano Pablos, María Isabel González Vasco, Misael Enrique Marriaga and Ángel Luis Pérez del Pozo, The Cracking of WalnutDSA: A Survey, in: Interactions between Group Theory, Symmetry and Cryptology, Symmetry 2019, 11(9), 1072 (doi:10.3390/sym11091072)

Further developments

The basic idea is still felt to be promising:

• Xiaoming Chen, Weiqing You, Meng Jiao, Kejun Zhang, Shuang Qing, Zhiqiang Wang, A New Cryptosystem Based on Positive Braids (arXiv:1910.04346)

• Garry P. Dacillo, Ronnel R. Atole, Braided Ribbon Group $C_n$-based Asymmetric Cryptography, Solid State Technology Vol. 63 No. 2s (2020) (JSST:5573)

But further attacks are being discussed:

• James Hughes, Allen Tannenbaum, Length-Based Attacks for Certain Group Based Encryption Rewriting Systems (arXiv:cs/0306032)

As are further ways around these:

• Xiaoming Chen, Weiqing You, Meng Jiao, Kejun Zhang, Shuang Qing, Zhiqiang Wang, A New Cryptosystem Based on Positive Braids (arXiv:1910.04346)