Paper 2021/397

SSProve: A Foundational Framework for Modular Cryptographic Proofs in Coq

Philipp G. Haselwarter, Aarhus University
Exequiel Rivas, Tallinn University of Technology
Antoine Van Muylder, KU Leuven
Théo Winterhalter, MPI-SP
Carmine Abate, MPI-SP
Nikolaj Sidorenco, Aarhus University
Catalin Hritcu, MPI-SP
Kenji Maillard, Inria Rennes
Bas Spitters, Aarhus University

State-separating proofs (SSP) is a recent methodology for structuring game-based cryptographic proofs in a modular way, by using algebraic laws to exploit the modular structure of composed protocols. While promising, this methodology was previously not fully formalized and came with little tool support. We address this by introducing SSProve, the first general verification framework for machine-checked state-separating proofs. SSProve combines high-level modular proofs about composed protocols, as proposed in SSP, with a probabilistic relational program logic for formalizing the lower-level details, which together enable constructing machine-checked cryptographic proofs in the Coq proof assistant. Moreover, SSProve is itself fully formalized in Coq, including the algebraic laws of SSP, the soundness of the program logic, and the connection between these two verification styles. To illustrate SSProve we use it to mechanize the simple security proofs of ElGamal and PRF-based encryption. We also validate the SSProve approach by conducting two more substantial case studies: First, we mechanize an SSP security proof of the KEM-DEM public key encryption scheme, which led to the discovery of an error in the original paper proof that has since been fixed. Second, we use SSProve to formally prove security of the sigma-protocol zero-knowledge construction, and we moreover construct a commitment scheme from a sigma-protocol to compare with a similar development in CryptHOL. We instantiate the security proof for sigma-protocols to give concrete security bounds for Schnorr's sigma-protocol.

Note: This manuscript to appear at TOPLAS is an improved and extended version of the CSF 2021 publication. The improvements we made throughout the text are too many to list exhaustively. At a high level we: (i) corrected the ElGamal security definition in §2.4; (ii) expanded the explanation of the logical rules in §4 and added new rules for assertions, one-sided memory accesses, and state invariants; (iii) significantly expanded the semantics section to be more self-contained and accessible, and to draw connections to related approaches (§5); (iv) added Sections 6 and 7 presenting two new case studies (KEM-DEM and Sigma-protocols); and (v) improved the related work section (§8). The paper has also gained a new author, and the author order has also slightly changed.

Available format(s)
Publication info
Published elsewhere. ACM Transactions on Programming Languages and Systems (TOPLAS)
high-assurance cryptographyformal verificationmodular cryptographic proofsstate-separating proofsCoq
Contact author(s)
philipp @ haselwarter org
erivas @ gmail com
antoine vanmuylder @ kuleuven be
theo winterhalter @ inria fr
catalin hritcu @ gmail com
kenji maillard @ inria fr
spitters @ cs au dk
2023-11-08: last of 7 revisions
2021-03-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Philipp G.  Haselwarter and Exequiel Rivas and Antoine Van Muylder and Théo Winterhalter and Carmine Abate and Nikolaj Sidorenco and Catalin Hritcu and Kenji Maillard and Bas Spitters},
      title = {SSProve: A Foundational Framework for Modular Cryptographic Proofs in Coq},
      howpublished = {Cryptology ePrint Archive, Paper 2021/397},
      year = {2021},
      doi = {10.1145/3594735},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.