Formalising $\varSigma $-Protocols and Commitment Schemes Using CryptHOL
Open Access
- 9 September 2020
- journal article
- research article
- Published by Springer Nature in Journal of Automated Reasoning
- Vol. 65 (4) , 521-567
Abstract
Machine-checked proofs of security are important to increase the rigour of provable security. In this work we present a formalised theory of two fundamental two party cryptographic primitives: $$\varSigma $$ -protocols and Commitment Schemes. $$\varSigma $$ -protocols allow a prover to convince a verifier that they possess some knowledge without leaking information about the knowledge. Commitment schemes allow a committer to commit to a message and keep it secret until revealing it at a later time. We use CryptHOL (Lochbihler in Archive of formal proofs, 2017) to formalise both primitives and prove secure multiple examples namely; the Schnorr, Chaum-Pedersen and Okamoto $$\varSigma $$ -protocols as well as a construction that allows for compound (AND and OR) $$\varSigma $$ -protocols and the Pedersen and Rivest commitment schemes. A highlight of the work is a formalisation of the construction of commitment schemes from $$\varSigma $$ -protocols (Damgard in Lecture notes, 2002). We formalise this proof at an abstract level using the modularity available in Isabelle/HOL and CryptHOL. This way, the proofs of the instantiations come for free.
Keywords
Funding Information
- Alan Turing Institute (EP/N510129/1)
This publication has 24 references indexed in Scilit:
- The Foundational Cryptography Framework2015
- Computer-Aided Security Proofs for the Working Cryptographer2011
- Formal certification of code-based cryptographic proofsACM SIGPLAN Notices, 2009
- The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs2006
- Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols2001
- On the Existence of Bit Commitment Schemes and Zero-Knowledge Proofs2001
- Wallet Databases with Observers2001
- How To Prove Yourself: Practical Solutions to Identification and Signature Problems2000
- On the (Im)possibility of Basing Oblivious Transfer and Bit Commitment on Weakened Security Assumptions1999
- Efficient signature generation by smart cardsJournal of Cryptology, 1991