💻 computer science

Cryptographic certificates of validity for trustworthy AI

This paper proposes a framework for trustworthy agentic AI by generating succinct cryptographic certificates that mathematically prove an agent's actions satisfy formally specified policies, enabling independent verification without re-execution or trust in the agent.

Original authors: Murdoch J. Gabbay

Published 2026-06-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Murdoch J. Gabbay

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: Trust the Proof, Not the Person

Imagine you are hiring a robot to book a flight for you. In the past, we trusted robots (or AI agents) because we knew who built them or because they had a digital signature saying, "I am from Company X."

But what if the robot is buggy, or what if it's a "Byzantine" robot (a fancy term for a robot that might be acting weirdly or maliciously)? A signature only proves who sent the message, not whether the message is correct or safe.

Murdoch Gabbay's paper proposes a new way to trust AI: Instead of trusting the robot's identity, we trust a cryptographic certificate that proves the robot's action follows the rules.

Think of it like this:

Old Way: You trust a chef because they wear a specific hat and have a license. You hope they didn't poison the soup.
New Way: The chef hands you a sealed, unbreakable receipt. This receipt mathematically proves that the soup was cooked at the right temperature, with the right ingredients, and no poison was added. You don't need to know the chef's name or watch them cook; you just check the receipt.

How It Works: The "Magic Translator"

The paper describes a three-step process to create these receipts.

1. Write the Rules (The "Law")

First, we take the rules we want the AI to follow (e.g., "Never spend more than $500" or "Only fly to countries with a travel advisory") and write them down in a strict mathematical language called logic.

Analogy: Imagine writing the rules of a board game in a language that a computer can understand perfectly, leaving no room for "maybe" or "I think."

2. The Translation (The "Compiler")

Next, we use a special tool (a compiler) to translate those logical rules into a math puzzle.

The Magic: The paper explains a clever trick where "True" becomes the number 0, and "False" becomes a positive number.
Analogy: Imagine a scale. If the AI followed the rules, the scale balances perfectly at zero. If the AI broke a rule, the scale tips and shows a heavy, positive number. The goal is to prove the scale is at zero.

3. The Certificate (The "Receipt")

The AI (or a helper) solves the math puzzle and generates a tiny, cryptographic proof. This proof says, "I have a secret solution that makes the scale balance at zero."

The Cool Part: A verifier (the person checking the AI) can look at this tiny proof and instantly know the rules were followed. They don't need to see the AI's private thoughts, they don't need to re-run the whole calculation, and they don't need to trust the AI. They just check the math.

A Concrete Example: The Power of Two

The paper uses a simple example of calculating $2^2$ (2 to the power of 2) to show how this works.

Imagine the AI claims, "I calculated $2^2 = 4$ ."
To prove this isn't a lie, the AI doesn't just say "4." It provides a derivation tree (a step-by-step history):

Step 1: $2^0 = 1$ (The starting point).
Step 2: $2^1 = 2$ (Based on Step 1).
Step 3: $2^2 = 4$ (Based on Step 2).

The cryptographic certificate proves that these steps are linked correctly. If the AI tried to skip a step or change a number, the math puzzle would fail, and the certificate would be invalid.

Why This Matters for AI Agents

The paper argues that as AI agents start doing real things (booking flights, approving invoices, deploying code), we need a way to verify their actions before they happen, not just look at logs afterwards.

No Re-Running: Checking the certificate is fast. You don't need to re-do the AI's work.
Privacy: Using "Zero-Knowledge" features, the AI can prove it followed the rules without revealing its private data (like your credit card number or secret strategy).
No Blind Trust: You don't have to trust the AI's developer. You only trust the math.

What This Paper Does NOT Do (Important Limits)

The author is very careful to state what this technology cannot do:

It doesn't write the rules for you. The certificate proves the AI followed the rules you gave it. If you wrote a bad rule (e.g., "Spend all the money"), the certificate will prove the AI followed that bad rule perfectly.
It doesn't guarantee safety. It only guarantees that the specific mathematical condition was met. It doesn't prove the condition itself was wise, ethical, or safe.
It doesn't replace human oversight. Humans still need to decide what the rules should be and audit the system.

Summary

This paper proposes a "Proof-Carrying Action" system for AI. Just as a driver might carry a license to prove they are allowed to drive, an AI agent would carry a cryptographic certificate to prove its action is correct.

It bridges the gap between Formal Logic (the rules) and Cryptography (the proof), allowing us to verify that an AI is behaving correctly without needing to trust the AI or see its private data. It's a way to say: "I don't trust you, but I trust the math you just handed me."

Based on the provided text, here is a detailed technical summary of the paper "Cryptographic certificates of validity for trustworthy AI" by Murdoch J. Gabbay.

Problem Statement

As AI systems transition from producing recommendations to executing autonomous actions (e.g., booking flights, approving invoices, deploying code), traditional assurance mechanisms become insufficient. Cryptographic signatures authenticate the origin of a message but cannot prove that an action satisfies specific correctness, safety, or compliance conditions in advance. Similarly, retrospective logging cannot prevent policy violations before they occur. The paper addresses the need for a mechanism to provide independently checkable evidence that an agent's action satisfies an agreed-upon formal policy before the action is accepted, without requiring the verifier to trust the agent's internal implementation or re-execute its computation.

Methodology

The paper proposes a framework for generating cryptographic certificates of validity by bridging formal logic and succinct cryptographic proofs. The methodology follows a three-step pipeline:

Formal Specification: The relevant policy or correctness condition is expressed as a logical predicate in a specific first-order logic.
Arithmetisation: This predicate is compiled into a witness-checking problem over polynomial constraints. The core mathematical contribution is a translation of first-order logic validity into judgements on polynomial constraints where:
- Truth (validity) is represented by the value 0.
- Falsehood (invalidity) is represented by a strictly positive value.
- Logical connectives are mapped to algebraic operations:
  - Equality ( $t=t'$ ) maps to $(t-t')^2$ .
  - Conjunction ( $\phi \land \psi$ ) maps to the sum $[\phi] + [\psi]$ .
  - Disjunction ( $\phi \lor \psi$ ) maps to the product $[\phi] \times [\psi]$ .
  - Universal quantification over a range is mapped to a summation over that range.
- Recursion and inductive definitions (e.g., exponentiation) are encoded by structuring the witness data as matrices where columns represent derivation steps, with pointers in a dedicated row ensuring the recursive structure is well-formed.
Cryptographic Certification: The agent (or an associated prover) generates a succinct cryptographic proof (potentially zero-knowledge) demonstrating that the polynomial constraints derived from the policy are satisfied by the specific action data.

The verification process involves the verifier checking the proof against a public key and parameters. If the proof verifies, the system accepts that the action satisfies the formal predicate, without needing to inspect the agent's private witness data or re-run the computation.

Key Contributions

Mathematical Translation: The paper provides a compact, application-agnostic arithmetisation of first-order logic validity into polynomial constraints (Definitions 2.3–2.7, Theorem 2.9). It demonstrates how to encode complex logical structures, including recursion and inductive derivations, into algebraic relations suitable for cryptographic backends.
Proof-Carrying Agent Actions: It conceptualizes agent actions as "proof-carrying" in a specific cryptographic sense. Unlike Proof-Carrying Code (PCC), which often requires inspecting source code, this approach allows untrusted, potentially black-box agents to provide succinct evidence of compliance.
Integration with Existing Tech: The framework is designed to interface with existing succinct argument systems (e.g., SNARKs, zkVMs like Cairo or RISC0) and polynomial commitment schemes (e.g., Halo2, Zinc). It positions the proposed logic as a high-level specification layer that compiles down to these cryptographic primitives.
Distinction from Runtime Verification: The approach differs from runtime verification by providing a pre-emptive, succinct certificate rather than a retrospective trace, and differs from standard PCC by not requiring the agent's internal design to be open or trusted, only that it can produce the certificate.

Results and Examples

The paper validates the approach through theoretical examples rather than empirical benchmarks:

Basic Logic: It demonstrates how truth values, equality, conjunction, disjunction, and range checks are encoded as polynomials that evaluate to zero if and only if the condition holds.
Recursive Computation: A detailed example encodes the inductive definition of exponentiation ( $a^b$ ). The paper shows how a matrix of witness data can encode a derivation tree, where rows 1–3 store input/output samples and row 4 stores pointers to previous steps. The validity predicate ensures these pointers form a well-formed recursive structure.
Robustness: The paper notes that a matrix might contain correct input-output values but fail the validity predicate if the "proof-carrying" structure (the pointers) is missing or malformed, illustrating that the certificate validates the derivation of the result, not just the result itself.

Significance and Scope

The paper positions this work as a "middle ground" between formal verification of source code and cryptographic authentication. Its primary significance lies in offering a cryptographic analogue of proof-carrying code for agentic AI systems.

The author explicitly notes the limitations and scope of the proposal:

Scope: The mathematical architecture is general and applicable to any domain where untrusted parties must provide checkable evidence of correctness. The specific application to AI agents is chosen because autonomous action creates an urgent need for pre-emptive assurance.
Limitations: A certificate of validity proves that a formal specification has been satisfied. It does not prove that the formal specification itself is the "right" one (i.e., that it correctly captures safety, legal, or ethical requirements). The paper emphasizes that closing the gap between formal predicates and real-world safety requires governance, auditing, and risk management processes (referencing NIST frameworks), which cannot be solved by mathematics or cryptography alone.
Future Work: The paper identifies the need for practical implementation details, including compiler design, benchmarking proving costs, and establishing governance for policy authoring and auditing.

In summary, the paper proposes a theoretical and mathematical foundation for attaching succinct, cryptographically verifiable proofs of policy compliance to AI agent actions, shifting the trust model from "trust the origin" to "trust the evidence."