Cryptographic certificates of validity for trustworthy AI

Murdoch J. Gabbay · 2026

Read Cryptographic certificates of validity for trustworthy AI by Murdoch J. Gabbay (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-23768.txt.

Introduction

Gabbay proposes attaching cryptographic proofs of policy compliance to the actions of AI agents, in a 2026 paper on trustworthy AI. AI agents increasingly act in the world: booking flights, approving invoices, deploying code. Signatures can prove who sent a message, and logs can reconstruct what happened, but neither proves in advance that an action satisfies agreed safety or compliance rules. Trust currently rests on origin, not on evidence about the action itself.

The proposal writes the policy condition as a formal logical predicate. It compiles the predicate into a witness checking problem over polynomial constraints. A succinct proof system then certifies the result, optionally with zero knowledge. The agent's action travels with its certificate, and anyone can verify compliance without trusting the agent or rerunning its work. The paper sketches the mathematics and the open questions in specification, auditing, and deployment.

Catalog record

CREATORMurdoch J. Gabbay
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.23768

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Cryptographic certificates of validity for trustworthy AI Murdoch J. Gabbay Abstract We propose cryptographic certificates of validity for agentic AI systems. The core idea is to formally specify a correctness or policy condition as a logical predicate, compile this predicate to a witness-checking problem over polynomial constraints, and use a succinct cryptographic proof system (and optionally zero-knowledge) to certify that the condition holds. This offers a middle ground between formal verification of source code, and cryptographic authentication. An agent’s action can be accompanied by an independently checkable proof that it satisfies an agreed formal policy, without requiring the verifier to trust the agent or to re-execute computation. We outline the approach at a high level, give the core mathematical translation, relate the proposal to proof-carrying code, zkVMs, formal methods, and agent governance, and note the specification, auditing, and deployment questions that a full implementation must answer. 1 Introduction Agentic AI systems are beginning to take actions, not merely produce recommendations. A travel assistant may book a flight; an enterprise agent may approve an invoice; a software agent may deploy code; a robotic agent may act in the physical world. For such systems a key question is: is this action authorised and policy compliant; is it correct? Cryptographic signatures traditionally authenticate origin , by certifying that the sender of a message knew a certain key. Logs can be used retrospectively to reconstruct events. However, cryptographic signatures, logs, and monitoring cannot prove that an action will satisfy correctness, safety, or compliance conditions in advance . In this paper, we propose a complementary mechanism: cryptographic certificates of validity for agent actions, before actions are carried out. The idea is simple. 1. Express the relevant policy or correctness condition as a formal specification in an appropriate logic. 2. Compile the resulting finite witness-checking problem to cryptography-friendly polynomial constraints (as we will sketch). 3. Require the agent or an associated prover to attach a succinct cryptographic proof that the constraints are satisfied. (In zero-knowledge settings, the verifier may check the certificate without learning private witness data.) The slogan is: do not trust an action because of its origin; trust it because it carries cryptographically checkable evidence of correctness. A note on scope may now be helpful. The mathematics in Section 2 is application-agnostic: it provides an arithmetisation of first‑order logic validity to judgements on polynomial constraints. This may be useful wherever a verifier requires succinct cryptographic evidence that a stated condition holds. This builds a bridge from first-order specification to cryptographic certification. The setting of agentic AI makes the assurance problem concrete and urgent — autonomous action is a signal case in which origin-based authentication and post-hoc logging may not be fully adequate. But the mathematical architecture which we use to address this problem — predicate \to polynomial constraint \to cryptographic certificate — is general, and might be usefully specialised to any domain where untrusted parties must provide checkable evidence of correctness. From this perspective, systems of AI agents are just heterogeneous distributed systems of agents who may be independently developed and may act according to their own priorities. They may also (to borrow a term from distributed systems) be Byzantine , meaning that they do not satisfy the expected specification. Our proposal is to make selected actions proof-carrying, in a very particular sense: for their action to be accepted, they must produce a cryptographic certificate of validity of their correctness predicate. Advanced AI assistants can plan and execute sequences of actions Gabriel et al. 2024 . Thus we need accountability, which requires evidence of where, why, how, and by whom agents are used Chan et al. 2024 . This paper offers a complementary assurance: further to identity, logging, and risk-management practices such as those articulated in the NIST AI Risk Management Framework National Institute of Standards and Technology 2023 , selected agent actions should carry compact certificates that a formal specification has been validated. We can think of this as a cryptographic analogue of proof-carrying code Necula 1997 , instantiated using succinct arguments and polynomial arithmetisation Thaler 2022 ; Gabbay 2024 ; Gabbay 2025 ; Garreta et al. 2025 . One final note, for the record: a certificate of validity for a formal specification does not in and of itself prove that the formal specification is the right specification. It proves, under the stated assumptions and to within appropriate soundness bounds of the underlying cryptographic back end, that the formal specification has been validated. 2 A compact slice of maths Notation 2.1 . Define [n]=\{1,\dots,n\}\subseteq\mathbb{N} . If R is a ring and X is a formal variable symbol then P\in R[X] is a formal sum of powers of X , which we call a polynomial (with coefficients in R ). Polynomials can be added and multiplied in the usual way. For example, (1+X)*(1-X)=1-X^{2}\in\mathbb{Z}[X] . Notation 2.2 . If P,Q\in\mathbb{Z}[X] then write P(Q)\in\mathbb{Z}[X] for the result of instantiating X to Q in P . For example if P=X+1 and Q=2*X then P(Q)=2*X+1 . \begin{array}[]{r@{\ }l}t::=&X\mid a\in\mathbb{Z}\mid t+t\mid t*t\mid{\text{$\mathtt{C}$}}_{i}(t)\mid{\text{$\mathsf{len}$}}({\text{$\mathtt{C}$}})\mid{\text{$\mathsf{reify}$}}(\phi)\\ \phi,\psi::=&t\mathbin{{\boldsymbol{\text{=}}}}t\mid\phi\mathbin{{\boldsymbol{\wedge}}}\phi\mid\phi\mathbin{{\boldsymbol{\vee}}}\phi\mid{{\boldsymbol{\hskip 0.8pt\raisebox{0.5pt}{\scalebox{.85}{$\forall$}}\hskip 0.2pt}}}_{\hskip-1.0pt{\text{$\mathtt{C}$}}}X.\phi\mid{\text{$\mathtt{C}$}}_{i}\mathbin{{\boldsymbol{<}}}t\mid t\mathbin{{\boldsymbol{<}}}{\text{$\mathtt{C}$}}_{i}\end{array} Above, i{\in}[{\text{$\mathit{arity}$}}({\text{$\mathtt{C}$}})] . These grammars are in BNF style, such that \phi and t to the right of ::= represent any predicate or term. Thus \phi\mathbin{{\boldsymbol{\wedge}}}\phi denotes a conjunction of two (possibly non-equal) predicates, and t\mathbin{{\boldsymbol{\text{=}}}}t denotes two (possibly non-equal) terms. Figure 1: Syntax of terms and predicates (Definition 2.3 ) Definition 2.3 . Fix an index variable symbol X and a set of polynomial function symbols {\text{$\mathtt{C}$}},{\text{$\mathtt{D}$}}\in{\text{$\mathsf{PolyFunc}$}} , each of which has a fixed but arbitrary arity {\text{$\mathit{arity}$}}({\text{$\mathtt{C}$}})\in\mathbb{N}_{\geq 1} . Write {\text{$\mathtt{C}$}}:n for the assertion “ {\text{$\mathtt{C}$}}\in{\text{$\mathsf{PolyFunc}$}} and {\text{$\mathit{arity}$}}({\text{$\mathtt{C}$}})=n ”. Define terms and predicates inductively as in Figure 1 . Notation 2.4 . We may write t\mathbin{{\boldsymbol{\leq}}}{\text{$\mathtt{C}$}}_{i}\mathbin{{\boldsymbol{\leq}}}t^{\prime} for (t-1\mathbin{{\boldsymbol{<}}}{\text{$\mathtt{C}$}}_{i})\mathbin{{\boldsymbol{\wedge}}}({\text{$\mathtt{C}$}}_{i}\mathbin{{\boldsymbol{<}}}t^{\prime}+1) . We may call predicates based on \mathbin{{\boldsymbol{<}}} range-checks . \begin{array}[]{r@{\ }l@{\ \ }r@{\ }l}{[\hskip-1.99997pt[X]\hskip-1.99997pt]}_{\varsigma}=&X&{[\hskip-1.99997pt[a]\hskip-1.99997pt]}_{\varsigma}=&a\\ {[\hskip-1.99997pt[t+t^{\prime}]\hskip-1.99997pt]}_{\varsigma}=&{[\hskip-1.99997pt[t]\hskip-1.99997pt]}_{\varsigma}+{[\hskip-1.99997pt[t^{\prime}]\hskip-1.99997pt]}_{\varsigma}&{[\hskip-1.99997pt[t*t^{\prime}]\hskip-1.99997pt]}_{\varsigma}=&{[\hskip-1.99997pt[t]\hskip-1.99997pt]}_{\varsigma}*{[\hskip-1.99997pt[t^{\prime}]\hskip-1.99997pt]}_{\varsigma}\\ {[\hskip-1.99997pt[{\text{$\mathtt{C}$}}_{i}(t)]\hskip-1.99997pt]}_{\varsigma}=&{\text{$\mathit{itplnt}$}}(\varsigma({\text{$\mathtt{C}$}})_{i})({[\hskip-1.99997pt[t]\hskip-1.99997pt]}_{\varsigma})&{[\hskip-1.99997pt[{\text{$\mathsf{len}$}}({\text{$\mathtt{C}$}})]\hskip-1.99997pt]}_{\varsigma}=&{\text{$\mathit{len}$}}(\varsigma({\text{$\mathtt{C}$}}))\\ {[\hskip-1.99997pt[{\text{$\mathsf{reify}$}}(\phi)]\hskip-1.99997pt]}_{\varsigma}=&{[\hskip-1.99997pt[\phi]\hskip-1.99997pt]}_{\varsigma}\\[8.61108pt] {[\hskip-1.99997pt[t\mathbin{{\boldsymbol{\text{=}}}}t^{\prime}]\hskip-1.99997pt]}_{\varsigma}=&({[\hskip-1.99997pt[t]\hskip-1.99997pt]}_{\varsigma}-{[\hskip-1.99997pt[t^{\prime}]\hskip-1.99997pt]}_{\varsigma})^{2}\\ {[\hskip-1.99997pt[\phi\mathbin{{\boldsymbol{\wedge}}}\phi^{\prime}]\hskip-1.99997pt]}_{\varsigma}=&{[\hskip-1.99997pt[\phi]\hskip-1.99997pt]}_{\varsigma}+{[\hskip-1.99997pt[\phi^{\prime}]\hskip-1.99997pt]}_{\varsigma}&{[\hskip-1.99997pt[\phi\mathbin{{\boldsymbol{\vee}}}\phi^{\prime}]\hskip-1.99997pt]}_{\varsigma}=&{[\hskip-1.99997pt[\phi]\hskip-1.99997pt]}_{\varsigma}*{[\hskip-1.99997pt[\phi^{\prime}]\hskip-1.99997pt]}_{\varsigma}\\ {[\hskip-1.99997pt[{{\boldsymbol{\hskip 0.8pt\raisebox{0.5pt}{\scalebox{.85}{$\forall$}}\hskip 0.2pt}}}_{\hskip-1.0pt{\text{$\mathtt{C}$}}}X.\phi]\hskip-1.99997pt]}_{\varsigma}=&\hbox to0.0pt{$\sum_{x{\in}[{\text{$\mathit{len}$}}(\varsigma({\text{$\mathtt{C}$}}))]}{[\hskip-1.99997pt[\phi]\hskip-1.99997pt]}_{\varsigma}(x)$\hss}\\[8.61108pt] {[\hskip-1.99997pt[{\text{$\mathtt{C}$}}_{i}<t]\hskip-1.99997pt]}_{\varsigma}=&\hbox to0.0pt{$\begin{cases}0&\forall j{\in}[{\text{$\mathit{len}$}}(\varsigma({\text{$\mathtt{C}$}}))].(\varsigma({\text{$\mathtt{C}$}})_{i,j}<{[\hskip-1.99997pt[t]\hskip-1.99997pt]}_{\varsigma}(j))\\ 1&\text{otherwise}\end{cases}$\hss}\\[8.61108pt] {[\hskip-1.99997pt[t<{\text{$\mathtt{C}$}}_{i}]\hskip-1.99997pt]}_{\varsigma}=&\hbox to0.0pt{$\begin{cases}0&\forall j{\in}[{\text{$\mathit{len}$}}(\varsigma({\text{$\mathtt{C}$}}))].({[\hskip-1.99997pt[t]\hskip-1.99997pt]}_{\varsigma}(j)<\varsigma({\text{$\mathtt{C}$}})_{i,j})\\ 1&\text{otherwise}\end{cases}$\hss}\end{array} In clauses mentioned in {\text{$\mathtt{C}$}}_{i} above, we insist on i\in[{\text{$\mathit{arity}$}}({\text{$\mathtt{C}$}})] for well-formedness. Figure 2: Polynomial semantics for terms and predicates (Definition 2.7 ) Notation 2.5 . An integer matrix is an element C\in\mathbb{Z}^{{\text{$\mathit{ar}$}}\times{\text{$\mathit{ln}$}}} where {\text{$\mathit{ar}$}}\in\mathbb{N} (for arity ) is the number of rows and {\text{$\mathit{ln}$}}\in\mathbb{N} (for length ) is the number of columns . Write {\text{$\mathit{len}$}}(C) for \mathit{ln} the number of columns in C , which we may call the length of C . Write C_{i} for the i th row in C (a vector of length {\text{$\mathit{len}$}}(C) ). Write C_{i,j} for the i,j -th element in C ; i is the row number and j is the column number. Definition 2.6 . Suppose \vec{a}=(a_{1},\dots,a_{n})\in\mathbb{Z}^{{\text{$\mathit{ln}$}}} is a \mathit{ln} -tuple of integers, for {\text{$\mathit{ln}$}}\in\mathbb{N} . Say that P\in\mathbb{Q}[X] interpolates \vec{a} at (1,2,\dots,{\text{$\mathit{ln}$}}) when \forall x\in[{\text{$\mathit{ln}$}}].P(x)=a_{x} . It is a fact ( Salgado and Wise 2022 , Chapter 9) that every \vec{a}\in\mathbb{Z}^{{\text{$\mathit{ln}$}}} can be interpolated by a unique polynomial interpolant {\text{$\mathit{itplnt}$}}(a_{1},\dots,a_{{\text{$\mathit{ln}$}}})\in\mathbb{Q}[X] of degree at most {\text{$\mathit{ln}$}}{\shortminus}1 , so {\text{$\mathit{itplnt}$}}(a_{1},\dots,a_{{\text{$\mathit{ln}$}}})(x)=a_{x} . 1 1 1 The Wikipedia page and this overview are excellent and very accessible introductions. Definition 2.7 . 1. An interpretation \varsigma assigns to {\text{$\mathtt{C}$}}\in{\text{$\mathsf{PolyFunc}$}} a matrix \varsigma({\text{$\mathtt{C}$}})\in\mathbb{Z}^{{\text{$\mathit{arity}$}}({\text{$\mathtt{C}$}})\times{\text{$\mathit{len}$}}(\varsigma({\text{$\mathtt{C}$}}))} . \varsigma({\text{$\mathtt{C}$}}) always has {\text{$\mathit{arity}$}}({\text{$\mathtt{C}$}}) rows; the number of columns depends on \varsigma . 2. Define semantics {[\hskip-1.99997pt[t]\hskip-1.99997pt]}_{\varsigma},{[\hskip-1.99997pt[\phi]\hskip-1.99997pt]}_{\varsigma}\in\mathbb{Q}[X] as in Figure 2 . 3. If

Read the complete text