A Higher-Order Indistinguishability Logic for Cryptographic Reasoning
David Baelde, Adrien Koutsos, Joseph Lallemand
Abstract
The field of cryptographic protocol verification in the computational model aims at obtaining formal security proofs of protocols. To facilitate writing such proofs, which are complex and hard to automate, Bana and Comon have proposed the Computationally Complete Symbolic Attacker (CCSA) approach, which is based on a first-order logic with a probabilistic computational semantics. Later, a meta-logic was built on top of the CCSA logic, to extend it with support for unbounded protocols and effective mechanisation. This meta-logic was then implemented in the SQUIRREL prover.
In this paper, we propose a careful re-design of the SQUIRREL logic, providing clean and robust foundations for its future development. We show in this way that the original meta-logic was both needlessly complex and too restrictive. Our new, higherorder logic avoids the indirect definition of the meta-logic on top of the CCSA logic, decouples the logic from the notion of protocol, and supports advanced generic reasoning and non-computable functions. We also equip it with generalised cryptographic rules to reason about corruption. This theoretical work justifies our extension of SQUIRREL with higher-order reasoning, which we illustrate on case studies.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
4 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- A Logic and an Interactive Prover for the Computational Post-Quantum Security of Protocols cites An Interactive Prover for Protocol Verification in the Computational Model
- Secrecy in Squirrel and the Post-Compromise Security of a Ratchet cites An Interactive Prover for Protocol Verification in the Computational Model
- Secrecy in Squirrel and the Post-Compromise Security of a Ratchet cites Foundations for Cryptographic Reductions in CCSA Logics
- Secrecy in Squirrel and the Post-Compromise Security of a Ratchet cites Leveraging Cryptographic Simulator Synthesis for Formally Verifying the FOO E-Voting Protocol
- CryptoVampire: Automated Reasoning for the Complete Symbolic Attacker Cryptographic Model cites A Logic and an Interactive Prover for the Computational Post-Quantum Security of Protocols
- CryptoVampire: Automated Reasoning for the Complete Symbolic Attacker Cryptographic Model cites An Interactive Prover for Protocol Verification in the Computational Model
- Foundations for Cryptographic Reductions in CCSA Logics cites A Logic and an Interactive Prover for the Computational Post-Quantum Security of Protocols
- Foundations for Cryptographic Reductions in CCSA Logics cites CryptoVampire: Automated Reasoning for the Complete Symbolic Attacker Cryptographic Model
- Foundations for Cryptographic Reductions in CCSA Logics cites An Interactive Prover for Protocol Verification in the Computational Model
- Leveraging Cryptographic Simulator Synthesis for Formally Verifying the FOO E-Voting Protocol cites An Interactive Prover for Protocol Verification in the Computational Model
- Leveraging Cryptographic Simulator Synthesis for Formally Verifying the FOO E-Voting Protocol cites Foundations for Cryptographic Reductions in CCSA Logics
Cited by top-tier papers4
- CryptoVampire: Automated Reasoning for the Complete Symbolic Attacker Cryptographic ModelSimon Jeanteur, Laura Kovács, Matteo Maffei, Michael RawsonS&P 2024 · 6 citations
- Leveraging Cryptographic Simulator Synthesis for Formally Verifying the FOO E-Voting ProtocolDavid Baelde, Adrien Koutsos, Justine SauvageUSENIX Security 2026 · 2 citations
- Secrecy in Squirrel and the Post-Compromise Security of a RatchetClément Hérouard, Charlie Jacomme, Adrien Koutsos, Joseph LallemandCCS 2026
- Foundations for Cryptographic Reductions in CCSA LogicsDavid Baelde, Adrien Koutsos, Justine SauvageCCS 2024
Builds on4
- ProVerif with Lemmas, Induction, Fast Subsumption, and Much MoreBruno Blanchet, Vincent Cheval, Véronique CortierS&P 2022 · 61 citations
- An Interactive Prover for Protocol Verification in the Computational ModelDavid Baelde, Stéphanie Delaune, Charlie Jacomme, Adrien Koutsos et al.S&P 2021 · 44 citations
- A Logic and an Interactive Prover for the Computational Post-Quantum Security of ProtocolsCas Cremers, Caroline Fontaine, Charlie JacommeS&P 2022 · 19 citations
- Curry and Howard Meet BorelMelissa Antonelli, Ugo Dal Lago, Paolo PistoneLICS 2022 · 3 citations
Related papers
- Automated Reasoning for Indistinguishability in the CCSASimon Jeanteur, Matteo Maffei, Laura Kovacs, Michael RawsonCCS 2026
- Mechanized Proofs of Adversarial Complexity and Application to Universal ComposabilityManuel Barbosa, Gilles Barthe, Benjamin Grégoire, Adrien Koutsos et al.CCS 2021 · 13 citations
- Robust Logical Foundations for Mechanizing Post-Quantum Cryptography in SquirrelDavid Baelde, Antoine Dallon, Stéphanie Delaune, Charlie Jacomme et al.CCS 2026
- Contextual Refinement of Higher-Order Concurrent Probabilistic ProgramsKwing Hei Li, Alejandro Aguirre, Joseph Tassarotti, Lars BirkedalPLDI 2026
- Cryptis: Cryptographic Reasoning in Separation LogicArthur Azevedo de Amorim, Amal Ahmed, Marco GaboardiPOPL 2026 · 1 citation
