ShannonProver: Towards Automating Formal Cryptographic Proofs

arXiv:2607.02847 · cs.CR, cs.PL · Submitted 2026-07-03 · Read on arXiv

Listen

Transcript

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.

UC Berkeley

cs.CR, cs.PL

Submitted: 2026-07-03

Updated: 2026-10-08

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 89/100

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

Key concepts

Proof Script Construction: This is the process where ShannonProver automatically writes the actual code or commands needed to prove a mathematical statement within a formal proof assistant. Instead of a human writing every step, an AI agent generates these specific proof scripts based on the overall security goal.
State-Aware Proof Context Management: This component compiles raw data from the verification checker into structured information that the AI agent can understand. It creates 'proof-state contexts' by projecting signals, building a semantic representation of the proof state, tracking resource availability, and summarizing actionable inspection points.
Multi-Agent Tree-Based Proof Orchestration: Proof construction is non-linear, meaning there are many different ways to proceed. This system manages multiple AI agents exploring different proof paths simultaneously using a tree structure. It decides when to spawn new agents or prune bad paths, ensuring thorough exploration of the proof space.

Terminology

Benchmark — 18× in this paper · explained in 2 episodes
Verification — 13× in this paper · explained in 2 episodes
AI Agents — 12× in this paper · explained in 2 episodes
Ablation — 12× in this paper · explained in 1 episode
Nadia — 9× in this paper · explained in 2 episodes
Abstraction — 8× in this paper · explained in 1 episode
Elias — 8× in this paper · explained in 2 episodes
Verifier — 7× in this paper · explained in 2 episodes
Agentic Framework — 6× in this paper · explained in 6 episodes
Pruning — 6× in this paper · explained in 4 episodes
Provenance — 3× in this paper · explained in 3 episodes
Core — 2× in this paper · explained in 2 episodes
Failure Modes — 2× in this paper · explained in 3 episodes
Formal Verification — 2× in this paper · explained in 2 episodes
Reinforcement Learning — 2× in this paper · explained in 4 episodes
Trace — 2× in this paper · explained in 2 episodes
Ablation study — 1× in this paper · explained in 1 episode
Actionability — 1× in this paper · explained in 3 episodes
Agentic System — 1× in this paper · explained in 2 episodes
Generative AI — 1× in this paper · explained in 2 episodes
Hallucination — 1× in this paper · explained in 3 episodes
Principles of Security and Trust — 1× in this paper

Summary

Cryptographic proofs are produced at a scale that increasingly exceeds human capacity for manual verification, necessitating automated proof engineering tools. ShannonProver presents an agentic framework designed to automate this process by constructing proof scripts for expressive proof assistants like EasyCrypt from a high-level security model and lemma decomposition. This work suggests a path toward accelerating cryptographic research by delegating the tedious, time-consuming task of formalizing proofs to agents, allowing cryptographers to iterate faster on new constructions and obtain machine-checked assurance earlier.

The gist

ShannonProver is an agentic framework that automates cryptographic proofs by constructing proof scripts for expressive proof assistants from a high-level security model and lemma decomposition.

Design Overview

ShannonProver targets the three phases of formal proof development: modeling the protocol and security definition (Phase I), decomposing the main theorem into intermediate lemmas (Phase II), and proving each lemma with a tactic-level proof script (Phase III). The system delegates Phase III completely to agents, providing feedback that helps cryptographers revise their decomposition choices when proof search stalls. To achieve this performance, ShannonProver utilizes two critical design ideas: state-aware proof context management and multi-agent tree-based proof orchestration.

State-Aware Proof Context Management

The first design component addresses the challenge of the agent needing to reconstruct state information from static project files during interaction with the checker. The paper introduces a proof-state compiler, which acts as a bridge between the agent and the EasyCrypt checker, assembling state-aware proof contexts. This compiler performs four cumulative passes:

State Projection (Layer 1): Canonicalizing raw verifier signals into one current committed snapshot, defining the cursor (the point in the proof from which to read state).
Proof-State IR (Layer 2): Building a typed semantic proof-state IR that classifies the goal kind and records layer-specific structure and candidate resources.
Resource Liveness and Program Frontier (Layer 3): Tracking resource liveness, determining which resources are live, blocked, or stale relative to the current program frontier.
Action Surface (Layer 4): Compiling the state information into a compact set of targeted inspection and probing actions, including resource references, binding references, inspection tools, probes, previews, and neutral diagnostics.

Multi-Agent Tree-Based Proof Orchestration

Proof construction is not linear; it involves choosing between several structurally different ways to proceed at any given proof state. ShannonProver handles this through a tree-based search policy where the agent extends a single branch of the proof tree. The orchestrator manages multiple branches across several agent instances, deciding when to spawn new agents, prune unproductive branches, or use negative memory to prevent agents from repeating failed tactics. This mechanism allows for spawning children when an agent stalls in a local neighborhood of bad moves and negative memory to record failures indexed by state shape.

Evaluation and Results

The evaluation involves two parts: a controlled ablation study isolating the proof-state compiler's effect on mechanical friction, and case studies on real-world protocols like ChaCha20-Poly1305, MEE-CBC, and CMAC. The metrics used are Error generation rate (fraction of rejected tactics) and Error friction (fraction of spend in unproductive windows). Results show that ShannonProver sharply reduces error friction across all lemma types, meaning the agent can immediately recover from mistakes. Furthermore, for invariant-synthesis and game-hop/reduction lemmas, the orchestrator case significantly increases the solve rate from 67% to 90%, demonstrating that diverse path exploration is crucial for these non-linear proof types. The cost analysis shows that most of the API cost is concentrated in the harder tail (invariant and game-hop lemmas), which ShannonProver handles effectively.

System Architecture

ShannonProver is implemented as a managed-prover architecture organized into three layers: the top layer for agent-facing search and proof-node management (deciding exploration strategy), the middle layer for managing a single proof node and showing the agent its structured view, and the bottom layer for contact with EasyCrypt (the semantic authority). This separation ensures that while the agent chooses moves, it does not own or decide when a proof is valid. The system lifts proof-script bookkeeping into a document model separate from the agent's reasoning budget.

Future Work

The paper suggests several promising directions for extension: scaling to larger projects like ML-KEM; moving upward from lemma proving to assisting in theorem decomposition; supporting verified implementations by extending the harness to include implementation context; and generalizing beyond EasyCrypt by viewing the harness-building as a compiler problem applicable to other formal verification settings. The ultimate goal is reserving human involvement for critical judgments while automating as much of the remaining proof-engineering work as possible.

References

[1] S.

Improvements for AI systems

Based on the provided paper, here are specific improvements for AI systems aimed at automating formal cryptographic proofs, detailing what these improved systems can achieve:

Upgrading from a Checker-in-the-Loop Baseline to a Proof-State Compiler Interface (ShannonProver Core):
Implementing State-Aware Proof Context Management via a Compiler Bridge:
Developing Multi-Agent Tree Orchestration for Complex Proof Search:
Enhancing Agent Reasoning through Explicit Resource Liveness and Frontier Analysis:
An improved AI system, powered by the ShannonProver framework, can achieve the following specific capabilities:

Area of Improvement Specific Capability of Improved System How it Achieves This (Mechanism) Impact on Cryptographic Research

:---:---:---:---

A. State-Aware Proof Context Management (via Proof-State Compiler) The system transforms raw checker output into a structured, typed compiled surface detailing the current proof layer, visible program structure, and relevant resources (lemmas, bridge lemmas). It explicitly tracks resource liveness and program frontiers. Eliminates semantic mislocalization. The agent stops guessing which lemma applies to a goal by name similarity; it reasons based on the compiler's explicit semantic context.

B. Precision in Tactic Selection (Action Surface) The system provides a compact action surface containing Resource References, Binding References (missing arguments), Inspection/Probe Tools, and Neutral Diagnostics. It shows the agent what to inspect or try next without changing the proof state itself. Prevents unconscious lowering and semantic mislocalization. The agent doesn't blindly try easy tactics; it chooses moves based on whether they preserve high-level resources (like call sites) or consume them, grounding its choices in state-aware information.

C. Robust Proof Strategy Exploration (Tree-Based Orchestration) The system employs a deterministic orchestrator managing multiple agent branches across a proof tree. It uses mechanisms like spawning new agents for stalled nodes, pruning unproductive branches based on progress gaps, and utilizing negative memory to prevent repeated failed tactics at the same state. Overcomes the limitations of single-agent backtracking. Instead of stalling on a dead end, the system systematically explores alternative routes (e.g., trying a different strategy from an earlier node) and avoids redundant effort across multiple agents.

D. Automated Phase III Engineering (End-to-End Automation) The system delegates the entire tactic-level proof script construction phase of formal verification to the agent, guided by the compiler's structured view, allowing cryptographers to delegate this tedious work entirely. Reduces expert effort from weeks/months (e.g., for ChaChaPoly1305 or MEE-CBC) down to hours or days. This accelerates research iteration cycles and brings trustworthy protocols from design to deployment faster, as the agent handles the mechanical engineering burden while experts focus on high-level modeling (Phase I) and decomposition (Phase II).

In summary, the improved AI system transforms from a reactive tactic executor into a proactive, state-aware proof engineer that manages its reasoning budget efficiently by providing explicit context to the LLM agent and employing sophisticated multi-agent search control.