Blog · arXiv Analysis · Last reviewed June 25, 2026

The Validity Certificate Becomes the Policy Proof

A June 2026 arXiv paper asks whether consequential agent actions can carry cryptographic evidence that a formal policy condition was satisfied.

For this essay, a validity certificate is a proof-bearing record attached to a proposed action. It says that a named formal predicate was satisfied under a named proof system. It does not say the agent is safe, the policy is wise, or the deployment is legitimate.

Origin Is Not Compliance

A signed agent action proves very little by itself. A signature can authenticate the key that produced or endorsed a message. A log can help reconstruct what happened after the fact. Neither one proves that a proposed action satisfies a safety rule, a compliance condition, a budget limit, or a formally stated authorization policy before the action is accepted.

That distinction matters as AI agents move from recommendation into action. A travel agent may buy a ticket. A software agent may deploy code. An enterprise agent may approve an invoice or update a system of record. The governance question is not only "who sent this?" It is "what exact condition was this action required to satisfy, and can an independent verifier check that condition without trusting the agent's internal story?"

The Paper Frame

The source is Murdoch J. Gabbay's Cryptographic certificates of validity for trustworthy AI, arXiv:2606.23768v1 [cs.CR], submitted June 22, 2026. The arXiv record lists the subjects as Cryptography and Security, Artificial Intelligence, and Logic in Computer Science.

The paper proposes cryptographic certificates of validity for agentic AI systems. The core path is: specify a correctness or policy condition as a logical predicate, compile that predicate into a witness-checking problem over polynomial constraints, and use a succinct cryptographic proof system, optionally with zero-knowledge, to certify that the condition holds. The paper positions this as a middle ground between full formal verification of source code and ordinary cryptographic authentication.

The paper is a proposal and mathematical bridge, not a deployed assurance standard. Its strongest contribution is vocabulary: an action can be accepted because it carries independently checkable evidence for a formal relation, rather than because the receiver trusts the agent's origin, prompt, log, or self-explanation.

Current Context

As of June 25, 2026, the arXiv record shows only version 1 of Gabbay's paper, submitted June 22, 2026. The right reading is early-stage research: useful for defining a possible proof-carrying action layer, not proof that agent assurance has been solved.

The current governance context makes the idea timely. NIST's AI Agent Standards Initiative is explicitly about trusted, interoperable, and secure agents capable of autonomous action, including agent authentication, identity infrastructure, and security evaluations. The April 2026 allied guidance Careful adoption of agentic AI services describes LLM-based agents as systems with tools, external data, memory, planning workflows, and action privileges, and warns against broad or unrestricted access, especially to sensitive data or critical systems.

Risk-management and regulatory sources point to adjacent evidence duties. NIST's Generative AI Profile is voluntary risk-management guidance for incorporating trustworthiness across the AI lifecycle. ISO/IEC 42001 is a management-system standard for establishing, implementing, maintaining, and improving an AI management system. The EU AI Act's high-risk system provisions include technical documentation, logging, and human oversight duties. None of those sources requires Gabbay-style cryptographic validity certificates, but all of them make the same governance pressure visible: consequential AI actions need evidence that can survive review.

A validity certificate would therefore sit beside, not above, those regimes. It can help prove a narrow formal condition about an action. It cannot replace an AI system inventory, safety case, conformity assessment, risk management process, incident reporting channel, human oversight mechanism, or affected-person remedy.

Predicate to Certificate

The mathematical center of the paper is a compact translation from first-order logic validity into polynomial constraints. The presentation uses a zero-versus-positive convention: success or validity is represented by zero, while failure is represented by a strictly positive value. Logical connectives are then mapped into polynomial operations in a way that lets validity become a checkable algebraic condition.

The paper illustrates the idea with a partial power-function example. Rows of a matrix can hold claimed input-output samples, while an additional row supplies proof-carrying structure by pointing to recursive premises. The useful lesson for agents is not the arithmetic example itself. It is the separation between a claimed output and a structured witness showing why the claim satisfies the formal rule.

In governance language, the predicate is the hard part. A predicate might express that an invoice is below a threshold, that an action stays inside an allowlisted destination, that a workflow used a current approval token, that a dataset commitment matches the approved evaluation set, or that a proposed tool call does not cross a declared data boundary. Those are only examples of the kind of thing that can become formal. The institution still has to decide whether the formal predicate is the right policy for the real risk.

What the Proof Proves

At an agent boundary, the paper sketches a certificate that binds a policy identifier, an action, public instance data, a verifier key, proof-system parameter hash, and a succinct proof. A policy author or operator fixes the predicate. A compiler maps that predicate and the action data into an algebraic relation. The agent, or a separate prover, supplies proof that private witness data satisfies the relation. The receiving system checks the proof and rejects the action if verification fails.

The important word is "relation." A verifier is not being asked to believe the agent, inspect all of its internals, or rerun its computation. It is checking whether the encoded formal claim has been proven under the approved proof system. In zero-knowledge settings, some witness data can remain hidden while the verifier still checks the statement. That is useful when the policy proof should not become a new disclosure channel.

The proof is therefore both powerful and narrow. It can prove that a witness satisfies a relation under specific cryptographic assumptions, parameters, verifier code, and public inputs. It does not prove that the witness was sourced lawfully, that the model understood the task, that the action is fair, that the policy reflects public values, or that the operator should have delegated the action in the first place.

The Certificate Boundary

A validity certificate is different from three nearby objects. A signature proves origin or possession of a key. A log preserves evidence that something happened. A safety case argues that a system or release boundary is acceptable given claims, evidence, mitigations, and residual uncertainty. A validity certificate proves one formal statement about one action or class of action.

That boundary keeps the tool honest. A proof-backed action should not be marketed as a safe action unless the safety claim is exactly the formal predicate being proved. A proof that a transaction stayed under a budget is not proof that the transaction was necessary. A proof that a model evaluation used a committed dataset is not proof that the dataset was representative. A proof that an agent had an approval token is not proof that the human approver understood the downstream consequences.

The strongest deployment pattern is layered: action certificates carry the portable governance record, runtime governance mediates actions before execution, audit trails preserve reviewable evidence, and validity certificates prove selected formal predicates where the claim can be made precise.

Governance Reading

The Spiralist reading is that a proof-backed action needs a receipt narrower than the word "safe." The receipt should say which policy predicate was used, which compiler version translated it, which proof back end and parameters were approved, what public action data was checked, what witness data remained private, what soundness assumptions apply, and who can challenge the policy itself.

This complements, rather than replaces, runtime governance pages already on the site. A portable action certificate records the action and its approval path. A validity certificate asks whether a formal predicate about that action has been cryptographically witnessed. Those are different trust objects. One preserves the governance trail. The other makes one formal claim independently checkable.

The governance problem is that proof systems can make weak policies look strong. The certificate may be mathematically sound while the predicate is incomplete, the compiler is stale, the verifier key is mismanaged, the public inputs are misleading, or the action is socially harmful in a way the relation never encoded. A proof can reduce trust in the agent's narration while increasing dependence on the policy author, compiler chain, verifier implementation, and proof-system setup.

That is not an argument against certificates. It is an argument for naming their place in the control stack. A certificate belongs at the acceptance boundary for selected actions, not as a general trust badge for the whole agent.

Limits and Failure Modes

The paper is careful about the largest limitation. A certificate of validity proves satisfaction of the encoded formal predicate under the assumptions and soundness bounds of the proof system. It does not prove that the predicate was the right one. It does not prove that the compiler is bug-free, that verifier parameters were governed well, or that the policy captures safety, legal, operational, or ethical requirements.

The failure mode is specification laundering. A system can turn a weak policy into a strong-looking proof. It can also hide governance inside compiler choices, verifier-key management, or proof-generation costs. A proof can reduce trust in the agent's internal narration while increasing dependence on the policy author, compiler chain, and cryptographic setup. That tradeoff is acceptable only if those dependencies are documented.

Other failure modes follow from the same boundary. Predicate drift occurs when policy changes but old predicates remain accepted. Compiler opacity appears when reviewers can read the policy text but not the translation that made it enforceable. Verifier capture appears when one vendor controls verifier code, keys, parameter updates, and pass/fail semantics. Witness-source blindness appears when the proof says the witness satisfies the relation but the system cannot show where the witness came from. Zero-knowledge overreach appears when privacy is used to hide evidence that a reviewer legitimately needs. Proof denial of service appears when proving cost, latency, or failure rates block legitimate work or push teams back to unverifiable bypasses.

There is also an affected-person problem. If an agent denies a service, changes a record, releases funds, files a report, or triggers enforcement because a proof verified, the affected person still needs a path to ask what policy was applied, what public inputs were used, who authored the policy, whether the predicate was current, and how an error can be corrected. Cryptographic validity without institutional contestability becomes a harder kind of opacity.

The Governance Standard

A serious validity-certificate regime should meet at least twelve tests.

First, register the predicate. The policy predicate should have an owner, purpose, version, scope, effective date, expiry or review date, and plain-language explanation.

Second, separate policy from compilation. Reviewers should be able to inspect the human policy, formal predicate, compiler version, generated constraints, test vectors, and known translation limits.

Third, bind public inputs. The action, policy identifier, model or agent identity, tool or destination, timestamp, verifier key, proof-system parameters, and relevant commitments should be part of the public instance or certificate envelope.

Fourth, define the witness boundary. The record should say what private data remains hidden, why hiding it is justified, who may inspect it under lawful process, and what metadata remains visible even in a zero-knowledge proof.

Fifth, govern keys and setup. Verifier keys, parameter hashes, trusted setup material where applicable, transparency claims, rotations, revocations, and emergency invalidation paths should be documented.

Sixth, make failure deterministic. The receiving system should say what happens when proof generation fails, verification fails, parameters are stale, the policy is expired, or the verifier cannot be reached. Fallback should not silently become "accept anyway."

Seventh, log the acceptance event. The system should preserve the certificate, verifier result, policy version, action outcome, rejection reason if any, and trace link in the AI audit trail.

Eighth, connect to human oversight. For consequential or high-risk actions, a valid proof may be necessary but not sufficient. Human reviewers still need the ability to understand, override, reverse, or escalate the action where law, policy, or domain risk requires it.

Ninth, test adversarially. Red teams should attack the predicate, compiler, witness generation, public input binding, replay protection, verifier update path, and user-interface language around "verified."

Tenth, prevent proof-washing. Interfaces and procurement documents should state exactly what was proven and what was not. A proof of policy compliance is not a proof of general safety, fairness, legality, or operational wisdom.

Eleventh, tie certificates to system inventory. The AI system inventory should record which agents, actions, tools, policies, proof systems, and verifiers rely on validity certificates.

Twelfth, preserve contestability. Affected users, auditors, deployers, and incident teams should have a documented route to challenge the predicate, public inputs, verifier version, witness source, or outcome.

Audit Receipt

The audit-grade sentence is: Gabbay proposes that selected agent actions carry cryptographic certificates proving that an agreed formal correctness or policy predicate has been satisfied after compilation into polynomial constraints.

The receipt is: a proof-backed agent action should be accepted only when the predicate, policy version, compiler version, public inputs, witness boundary, proof back end, verifier key, parameter hash, soundness assumptions, rejection behavior, and policy-review path are visible.

The shorter procurement rule is: no certificate without a statement. A buyer or regulator should not accept "cryptographically certified" as a complete assurance claim unless the seller can show the exact statement, relation, witness boundary, verifier, assumptions, version, and operational consequence.

Source Discipline

Use Gabbay's arXiv paper for the proposal, mathematical translation, proof-carrying-action frame, related-work positioning, and stated open questions. Do not use it as evidence that any production agent platform currently implements the scheme or that cryptographic validity certificates are a recognized compliance standard.

Use NIST's zero-knowledge material for the public-statement, witness, and privacy-enhancing-cryptography framing. Use NIST AI RMF materials, ISO/IEC 42001, the EU AI Act, and allied agentic-AI guidance for governance context, not as proof that Gabbay's mechanism satisfies those regimes. Use W3C Verifiable Credentials only as a standards analogy for claim, issuer-holder-verifier, and tamper-evidence concepts, not as an agent-policy-proof standard.

Source discipline matters because "certificate" is an overloaded word. A cryptographic validity certificate, an ISO management-system certificate, a conformity-assessment certificate, a verifiable credential, a digital signature certificate, and an internal safety-case approval are different artifacts. The article should not let one borrow legitimacy from another without showing the exact claim being certified.

Sources

Return to Blog