Toward cryptographically verifiable authorization for autonomous AI agents: A security hypothesis, preliminary formal model, and proof-of-concept implementation

Source: arXiv:2607.21325 · Published 2026-07-23 · By M. Llambí-Morillas, D. Fernández-Fernández

TL;DR

This paper addresses a foundational gap in the security of autonomous AI agents, which increasingly perform actions with limited human oversight and dynamic execution contexts. Traditional authentication and delegation mechanisms do not provide cryptographic proofs that a specific request by a given agent satisfies the applicable authorization policy in that execution context. The authors hypothesize that such authorization decisions can be formalized as a cryptographically verifiable relation (RCVA) that jointly binds agent identity, concrete requests, execution context, and policy compliance while preserving attribute privacy.

To this end, the paper presents a preliminary formal model of Cryptographically Verifiable Agent Authorization (CVA), defines a minimal set of desired security properties—authorization soundness, principal binding, request binding, policy binding, and replay resistance—and demonstrates a proof-of-concept implementation based on zk-SNARKs (Groth16). It highlights an important conceptual separation between identity, authorization request, and execution evidence as distinct security objects. The implementation uses zero-knowledge proofs to cryptographically bind authorization evidence to a request without revealing private data. The work surfaces open problems, including the mismatch between authorization bindings and runtime execution bindings, and proposes a falsifiable research agenda for further investigation.

Key findings

• Authorization soundness requires that no proof can be accepted without a valid witness; adversary success probability decreases negligibly with security parameter lambda (Equation 28).
• Principal binding holds that a proof for one agent identity cannot be accepted as valid for another distinct identity, assuming the binding property of the identity commitment (Equation 29).
• Authorization-request binding ensures proofs are bound to a specific request and cannot be reused to authorize different requests (Equation 30).
• Policy binding enforces that a proof generated under one policy version pidj cannot be accepted under a different policy version pidk (Equation 31).
• Context binding prevents substitution of the execution context commitment at authorization: proofs cannot verify under altered context commitments (Equation 36).
• Replay resistance is achieved via nonce and timestamp freshness checking outside the proof system—nonces must be single-use and timestamps valid within a window (Equations 38-40).
• The proof-of-concept prototype uses Groth16 zk-SNARKs, with agent identifiers instantiated by a deterministic Poseidon hash instead of a randomized commitment, realizing principal and request binding but not randomized hiding semantics.
• A structural limitation identified is that authorization binding (via proofs) is logically distinct from runtime execution binding—proofs do not guarantee that the authorized action is the action executed (Equation 43), necessitating additional runtime trust mechanisms.

Threat model

The adversary is an efficient polynomial-time attacker capable of observing, intercepting, substituting, and replaying authorization proofs and statements, as well as controlling unauthorized or partially authorized agents. The adversary cannot break underlying cryptographic primitives (such as zk-SNARK knowledge soundness or hash collision resistance), cannot obtain honest parties’ secret keys, nor compromise the trusted authorization gateway enforcing freshness and replay resistance. The threat model focuses on attacks targeting the binding and soundness properties of the authorization evidence itself.

Methodology — deep read

1. Threat Model & Assumptions: The adversary is a probabilistic polynomial-time entity capable of intercepting, replaying, substituting proofs, forging proofs, modifying request commitments, substituting policy identifiers, and controlling unauthorized or partially authorized agents. The adversary cannot break underlying cryptographic primitives, learn secret keys of honest agents, or compromise the trusted authorization gateway.

2. Data & Models: The system models autonomous agents (A), gateways/verifiers (G), external callable tools (T), protected resources (R), and authorization policies (P). An authorization request qi = (idi, α, res, c, pidj, n, t) includes a cryptographic commitment to the agent identity (idi), requested action α, resource res, execution context c, a policy identifier pidj, nonce n, and timestamp t. Actions and contexts are canonically serialized and committed via collision-resistant hashes (Hq, Hc) to maintain consistency and bind requests and contexts to proofs.

3. Architecture & Algorithm: The core cryptographic relation RCV A(x,w) returns 1 if and only if the witness w correctly opens commitments in public statement x and the private attributes satisfy the referenced policy Pj. The public statement includes idi, request commitment hq, context commitment hc, policy id pidj, nonce n, and timestamp t. The private witness w contains secret keys, attributes, and preimages of the public commitments. The authorization proof π is a zero-knowledge proof of knowledge for this relation, generated and verified using Groth16 zk-SNARK over elliptic curve bn128.

The relation enforces principal binding by requiring knowledge of a secret key opening idi, request binding by ensuring the proof corresponds to the committed request hq, context binding for hc, and policy binding for pidj. Replay resistance is enforced externally by tracking nonce reuse and timestamp validity.

4. Training Regime: Not applicable; this is a formal-cryptographic construction and implementation rather than a machine learning model. The proof system uses trusted setup parameters generated for the Groth16 zk-SNARK.

5. Evaluation Protocol: The paper defines five cryptographic security games addressing proof forgery, cross-principal reuse, cross-request reuse, cross-policy reuse, and replay attacks. Security guarantees rely on standard assumptions about knowledge soundness of zk-SNARKs and binding properties of cryptographic commitments. The prototype demonstrates feasibility via a Circom 2.x circuit verifying possession of the secret key and policy satisfaction predicates implemented as arithmetic constraints. Efficiency metrics, probabilistic bounds, and exact numerical evaluation of soundness are left for future quantitative analysis.

6. Reproducibility: The paper reports a public proof-of-concept implementation available prior to this formalization. Source code, specific circuit definitions, and detailed policy encodings are not included in the paper, limiting immediate end-to-end reproducibility. Future work proposes releasing code and comparing alternate cryptographic proof systems for post-quantum security and trusted setup minimization.

One concrete example follows: an autonomous agent commits to its identity idi using Poseidon(ski), constructs a canonical serialization of its requested action plan 'plan', hashes it with SHA256 to hplan, and submits proof π that it knows ski opening idi and that attrsi and plan satisfy the authorized policy PP oC. The gateway verifies π against xP oC = (idi, hplan, n, t), checks nonce freshness, and if valid, accepts authorization without learning private witness w.

Technical innovations

• Formulation of authorization decisions for autonomous AI agents as a cryptographically verifiable relation (RCVA) binding principal, concrete request, execution context, and policy satisfaction.
• Definition of a compact but comprehensive set of candidate security properties specific to agent authorization, including authorization soundness, principal/request/policy/context binding, and replay resistance.
• Separation of identity evidence, authorization evidence, and execution evidence as distinct, individually verifiable security objects, exposing a missing link in current agent security frameworks.
• Proof-of-concept implementation of request-bound authorization using Groth16 zk-SNARKs instantiated with efficient Poseidon and SHA256 commitments, demonstrating constructive feasibility despite trade-offs.

Limitations

• The proof-of-concept uses a deterministic Poseidon hash for agent identity instead of a full randomized commitment scheme, weakening privacy guarantees.
• The trusted setup of Groth16 zk-SNARKs limits post-quantum security and introduces trust assumptions not yet addressed.
• Replay resistance depends on external mutable gateway state for nonce and timestamp freshness, not internal to the cryptographic relation.
• The formal model and prototype do not address the critical gap between authorization-binding proofs and ensuring the authorized action is the actually executed runtime action (TOCTOU issues).
• No comprehensive quantitative security evaluation or performance benchmarking is provided; efficiency and scalability analysis are future work.
• The model assumes a trusted authorization gateway and does not consider compromise or insider threats affecting enforcement.

Open questions / follow-ons

• How to extend the model and proof system to include a cryptographically verifiable linkage between authorization proofs and actual runtime action execution, closing the authorization-execution binding gap?
• Can randomized commitment schemes for agent identity be efficiently incorporated to realize stronger privacy guarantees in authorization proofs?
• What are the trade-offs of adopting post-quantum zero-knowledge proof systems (e.g., STARKs) for scalable agent authorization versus trusted setup zk-SNARKs?
• How to design stateful but privacy-preserving authorization gateways that balance replay resistance, policy freshness, and scalability in multi-agent environments?

Why it matters for bot defense

For bot-defense and CAPTCHA practitioners, this work provides a foundational cryptographic framework to securely establish that a specific autonomous agent’s request satisfies authorization policies in dynamic real-world contexts. Unlike conventional authentication or delegation, CVA binds authorization cryptographically at the request level, which can greatly enhance trust when AI-driven agents interact with protected resources or sensitive operations.

Practitioners designing CAPTCHA or bot-detection layers could leverage such zero-knowledge proof techniques to validate agent permissions without disclosing sensitive attributes, enabling privacy-preserving access controls. The clear separation between identity, authorization, and execution evidence also highlights potential security gaps in current bot-defense architectures that only authenticate identity but do not cryptographically verify request compliance with up-to-date policies or runtime contexts. However, as the current implementations require trusted gateways and actively maintained replay control state, practical adoption will need careful engineering to integrate with existing bot-defense enforcement infrastructure and address the execution binding gap to prevent misuse post-authorization.

Cite

@article{arxiv2607_21325,
  title={ Toward cryptographically verifiable authorization for autonomous AI agents: A security hypothesis, preliminary formal model, and proof-of-concept implementation },
  author={ M. Llambí-Morillas and D. Fernández-Fernández },
  journal={arXiv preprint arXiv:2607.21325},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.21325}
}

Read the full paper

• arXiv:2607.21325 (abstract)
• arXiv:2607.21325 (PDF)