ShannonProver: Towards Automating Formal Cryptographic Proofs

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: I'm Nadia, and with me are Elias and Priya, guest researcher.

Elias: Today's paper: "ShannonProver: Towards Automating Formal Cryptographic Proofs".

Nadia: Cryptographic proofs are produced at a scale that increasingly exceeds human capacity for manual verification, necessitating automated proof engineering tools.

Elias: First, who's behind it and why it matters.

Title and authors: Nadia: So, we're looking at the paper titled "ShannonProver: Towards Automating Formal Cryptographic Proofs," and it seems to be tackling a real headache in cryptography. It suggests a way to automate the tedious process of writing proof scripts for tools like EasyCrypt.

Elias: Exactly, I see that title, and what catches my eye is that it's focused on moving away from manual proof engineering towards something more automated. It implies they're trying to solve the bottleneck where even if you have a good plan for the proof, actually writing the specific steps in a formal language is too much work for a human to do efficiently.

Priya: From my side, I wonder what this automation means for us in terms of understanding protocols; does it just make writing proofs faster, or does it open up new ways to analyze security properties that we couldn't touch before?

Nadia: Well, the core idea is that this framework aims to build proof scripts automatically starting from a high-level security model and a decomposition of the main theorem into smaller lemma obligations. It’s about taking the big picture and letting an AI handle the nitty-gritty script writing for those smaller pieces.

Elias: That decomposition step is key, isn't it? They are delegating Phase III—the tactic-level proof script construction—completely to agents, which used to be a major time sink. It promises that if the agents find a valid proof script, the cryptographer can move on immediately without having to write those specific tactics by hand.

Priya: I think that speed is important, especially when we are looking at complex protocols where the proof work for something like ChaCha20-Poly1305 took months and required lots of creative effort to interlace things. Does this framework really cut down that time significantly?

The paper's summary: Nadia: The paper summarizes ShannonProver as an agentic framework designed to automate cryptographic proofs by constructing proof scripts for expressive proof assistants from a high-level security model and lemma decomposition. It lays out three distinct phases of formal proof development: modeling the protocol and security definition, decomposing the main theorem into intermediate lemmas, and finally proving each lemma with a tactic-level proof script.

Elias: That three-phase structure is what I find interesting because it mirrors the actual workflow cryptographers follow in many large projects. The paper emphasizes that Phase III is where the heavy, time-consuming mechanical engineering happens, and ShannonProver intends to handle that delegation entirely to agents.

Priya: What I’m really taking away from that summary is the feedback loop they built into it: if proof search stalls or a timeout occurs during Phase III, the framework provides feedback that helps the human revise their initial decomposition choices in Phase II, which is quite smart for catching conceptual errors early.

Nadia: It really suggests a shift where cryptographers spend less time on mechanical script writing and more time on high-level modeling and making sure their lemma decomposition makes sense before they even start scripting. It’s about letting the AI handle the tedious part of formalization.

Elias: And that leads into how they manage the proof context, which seems crucial for the agents to work effectively within an environment like EasyCrypt without getting lost in static project files. They introduce a state-aware compiler to bridge this gap between raw checker output and what the agent actually needs to see.

Priya: That sounds like a necessary piece of infrastructure; if the agent can't reliably reconstruct the current state of the proof—what resources are live, what's blocked—then its ability to generate correct tactics is severely limited, so that compiler seems foundational.

The paper's improvements: Nadia: Beyond just automating Phase III, the paper suggests two major design ideas to make this agentic framework work well: first, state-aware proof context management and second, multi-agent tree-based proof orchestration.

Elias: The state-aware compiler is a big piece of engineering here; it performs four cumulative passes—State Projection, Proof-State IR building, Resource Liveness and Program Frontier tracking, and Action Surface compilation—to create these structured contexts for the agent. It essentially turns raw verifier signals into something that's meaningful to the LLM.

Priya: I’m curious about that resource liveness part; tracking what resources are "live," "blocked," or "stale" relative to the current program frontier sounds like it gives the agent a much more intelligent way to decide which tactics are actually viable at any given moment in the proof.

Nadia: And on top of that, they have this multi-agent tree-based proof orchestration system. This isn't just one agent doing one thing; it manages multiple branches across several agents, deciding when to spawn new agents if a branch stalls or prune unproductive paths.

Elias: That branching and pruning mechanism is what I think really addresses the non-linear nature of proof construction where you can't always follow a straight line. The negative memory feature also helps prevent the agents from repeating tactics that have already failed at similar states, which cuts down on wasted computation.

Conclusion: Nadia: So, to wrap up this discussion on "ShannonProver: Towards Automating Formal Cryptographic Proofs," we've seen how this agentic framework tackles the proof engineering bottleneck by automating the script construction phase from a high-level security model and lemma decomposition.

Elias: We've discussed how they solve this through state-aware context management and multi-agent orchestration, showing that even complex proofs like invariant-synthesis and game-hop/reduction lemmas can see significant increases in their solve rates, jumping from sixty-seven percent to ninety percent.

Priya: I think the real implication here is that if we can reliably get these systems working on real protocols, it means we could start getting machine-checked assurance for things that currently take months of human effort to formalize. That's a big shift in how quickly we can move from design to deployment.

Nadia: It sounds like the paper points toward reserving human involvement for those critical judgments and high-level modeling work, while letting the AI handle the mechanical proof engineering burden automatically for us. We’re getting ready to look at what comes next in this area of research.

Elias: Indeed, ShannonProver provides a concrete path forward for accelerating cryptographic research by delegating that tedious, time-consuming task of formalizing proofs to agents, allowing cryptographers to iterate faster on new constructions and obtain machine-checked assurance earlier.

Priya: It's exciting to see this level of structured approach being applied to real cryptographic primitives like MEE-CBC or CMAC; I look forward to seeing how these results scale up in future work.

Nadia: Well, that concludes our discussion on ShannonProver, and we'll be back soon with more updates from the arXiv.