nLab cryptography

Idea

(…)

Related entries

• arithmetic cryptography

• digital identity,

• information theory,

• quantum cryptography, quantum information theory

• quantum computing,

• blockchain

• zoranskoda: computer security, blockchain, blockchain security, digital identity

References

General

• Wikipedia, Outline of cryptography, public-key cryptography, cryptographic protocol, authentication, zero-knowledge proof, non-interactive zero-knowledge proof, OAuth, homomorphic encryption

• post-quantum cryptography at nist.gov

probabilistic:

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

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)

Verified software

On verified software for cryptography:

• Mihhail Aizatulin, Franccois Dupressoir, Andrew D. Gordon, Jan Jürjens, Verifying Cryptographic Code in C: Some Experience and the Csec Challenge (pdf)

• Mihhail Aizatulin, Andy Gordon, Jan Jürjens, Extracting and Verifying Cryptographic Models from C Protocol Code by Symbolic Execution, CCS ‘11 Proceedings of the 18th ACM Conference on Computer and Communications Security 2011 (pdf)

• Matthias Berg, Formal Verification of Cryptographic Security Proofs, 20013 (pdf, doi:10.22028/D291-26528)

• Adam Petcher, A Foundational Proof Framework for Cryptography, 2014 (pdf, harvard:17463136)

• Adam Petcher, Greg Morrisett, The Foundational Cryptography Framework, In: R. Focardi, A. Myers (eds.) Principles of Security and Trust POST 2015. Lecture Notes in Computer Science, vol 9036. Springer, Berlin, Heidelberg (doi:10.1007/978-3-662-46666-7_4)

• Andrew W. Appel, Verification of a Cryptographic Primitive: SHA-256, ACM Transactions on Programming Languages and SystemsApril 2015 Article No.: 7 (doi:10.1145/2701415, pdf)

• Andres Erbsen, Jade Philipoom, Jason Gross, Robert Sloan, Adam Chlipala, Simple High-Level Code for Cryptographic Arithmetic - With Proofs, Without Compromises, 2019 IEEE Symposium on Security and Privacy (SP) $[$doi:10.1109/SP.2019.00005$]$

• Mihhail Aizatulin, Verifying Cryptographic Security Implementations in C Using Automated Model Extraction (arXiv:2001.00806)

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:

• Paventhan Vivekanandan, A Homotopical Approach to Cryptography, talk at FCS 2018 (pdf, easychair:GLtQ#), In: Charles Morisset and Limin Jia (eds.) FCS Informal Proceedings 55 (2018)

• Paventhan Vivekanandan, HoTT-Crypt: A Study in Homotopy Type Theory based on Cryptography, Kalpa Publications in Computing Volume 9, 2018, Pages 75-90 (doi:10.29007/tvpp, web slides, pdf)

category: applications, computer science