nLab cryptography








  • Shafi Goldwasser, Silvio Micali, Probabilistic encryption, Journal of Computer and System Sciences 28:2 (1984) 270-299

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”).

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)


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)


  • 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)


  • 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 nC_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)

Verified software

On verified software for cryptography:

On type theory for verified cryptography:

  • Cédric Fournet, Karthikeyan Bhargavan, Andrew D. Gordon, Cryptographic Verification by Typing for a Sample Protocol Implementation, In: Aldini A., Gorrieri R. (eds) Foundations of Security Analysis and Design VI. FOSAD 2011. Lecture Notes in Computer Science, vol 6858. Springer (2011) (doi:10.1007/978-3-642-23082-0_3)

  • Cédric Fournet, Markulf Kohlweiss, Pierre-Yves Strub, Modular code-based cryptographic verification, CCS ‘11: Proceedings of the 18th ACM conference on Computer and communications securityOctober 2011 Pages 341–350 (doi:10.1145/2046707.2046746)

On homotopy type theory for verified cryptography:

Last revised on October 8, 2022 at 18:13:41. See the history of this page for a list of all contributions to it.