Toward cryptographically verifiable authorization for autonomous AI agents: A security hypothesis, preliminary formal model, and proof-of-concept implementation M. Llambí-Morillas 1
1,†
D. Fernández-Fernández
2
Universidad Tecnológica Atlántico-Mediterráneo (UTAMED) 2 Universidad de Santiago de Compostela (USC)
arXiv:2607.21325v1 [cs.CR] 23 Jul 2026
July 24, 2026
Abstract. Autonomous AI agents increasingly execute actions, invoke tools, and operate on protected resources with limited human oversight. Existing authentication and authorization mechanisms establish identity and delegate authority, but do not inherently provide cryptographic evidence that a concrete request issued by a specific agent satisfies the applicable policy in a specific execution context. This paper hypothesizes that agent authorization can be formalized as a cryptographically verifiable relation, denoted RCV A , that jointly binds an agent principal, a concrete authorization request, an execution context, and the satisfaction of an applicable policy, while selectively preserving the confidentiality of private authorization attributes. We introduce a preliminary formal abstraction for Cryptographically Verifiable Agent Authorization (CVA), define a compact set of candidate security properties including authorization soundness, principal binding, request binding, policy binding, and replay resistance, and provide an executable zero-knowledge proof of concept that instantiates selected elements of the model over a Groth16 zk-SNARK construction. We further identify and formalize the structural separation among identity binding, authorization-request binding, and runtime execution binding as a central open problem in the design of secure agentic systems (a distinction not explicitly addressed by current agentic security frameworks) and present a falsifiable research agenda for its resolution. Keywords: autonomous AI agents, zero-knowledge proofs, verifiable authorization, agentic security, zkSNARKs, access control, cryptographic authorization, cryptographic protocols, zero-trust architecture, preexecution authorization.
1. Introduction — Autonomous AI agents are no longer passive software clients. They are increasingly designed to invoke tools, call API, access protected resources, construct multi-step action sequences, delegate subtasks, and act on external resources with limited human supervision. This transition from deterministic client behavior to autonomous, context-dependent request generation changes the security object over which authorization mechanisms must reason. In such systems, it is insufficient to establish only who or what an agent is, or whether a credential has been delegated; the system must determine whether a concrete request, produced by a concrete agent under a concrete execution context, satisfies an applicable policy. Let Ai ∈ A denote an autonomous agent, qi an authorization request issued by Ai , α a requested action to execute, res a concrete resource to access, c an execution context, and Pj an applicable policy (the symbol P is reserved for the set of policies, Subsection 3.1). The distinction motivating this work can be expressed as: AuthN(Ai ) ⇏ AuthZ(Ai , α, res, c, Pj ) (1)
but neither is sufficient to establish that a concrete request is authorized. Similarly, if a principal user U delegates a capability κ to agent Ai : Delegate(U, Ai , κ) ⇏ AuthZ(qi ).
Delegation may establish authority over a broad class of operations, while the permissibility of a concrete request qi may still depend on the target resource (res ∈ R), the execution context (c, which may encode risk level, environment classification, or session state), the applicable policy version (pid j ), and temporal validity (t). These attributes are defined formally as components of the authorization request in Subsection 3.1; they are enumerated here to make explicit that delegation alone does not determine the permissibility of any specific request. This observation is not isolated to the present work. Recent institutional analyses have characterized what ISACA [1] terms “the looming authorization crisis” (the systematic failure of existing IAM frameworks, including OAuth 2.0 [2], OpenID Connect, and SAML) when applied to agentic systems that violate their foundational assumptions of deterministic behavior and a single authenticated principal. The OpenID Foundation [3] has similarly identified the insufficiency of adapting existing protocols and proposed new identity management primitives for agentic contexts. The present work complements these analyses by providing
or in its simplified form: AuthN(Ai ) ⇏ AuthZ(qi ).
(3)
(2)
The symbol ⇏ is used intentionally. It does not denote message flow, but logical non-implication: authentication or delegation may be necessary for authorization, 1
a formal characterization of the gap: not merely as an architectural insufficiency, but as a missing security property: namely, the absence of a cryptographically verifiable relation binding a specific agent request to policy satisfaction.
Formally, we postulate the existence of a relation: RCV A (x, w) ∈ {0, 1},
(4)
Let λ denote the cryptographic security parameter. The proof-system parameters are generated with respect to the authorization relation:
This gap has become consequential only recently, as AI agents have transitioned from controlled pipelines to open agentic architectures, that is, systems in which an agent may autonomously select tools, construct multistep action plans, and act upon external resources in ways not anticipated at deployment time. In this setting, the permissibility of a concrete request cannot be determined at authentication time, but must be evaluated at request time against a policy that may depend on dynamic runtime attributes.
pp ← Setup(1λ , RCV A ),
(5)
where pp abstracts the public parameter material required for proving and verification, such as circuitspecific proving and verification keys in a SNARK implementation. Let π denote the generated proof. Then: π ← Prove(pp, x, w),
Recent work has advanced decentralized agent identity [4], accountable execution [5], zero-trust agent architectures [6], ZKP-based policy compliance [7], delegation, and privacy-preserving audit. A zero-knowledge proof (ZKP) is a cryptographic protocol in which a prover demonstrates the truth of a statement to a verifier without revealing any information beyond the validity of that statement itself [8]. The contribution of this paper is therefore not the generic application of zero-knowledge proofs to agentic systems. Instead, we investigate a narrower and more precise question: whether authorization itself can be represented as a request-bound cryptographically verifiable relation, distinct from identity authentication, capability delegation, and post-hoc audit. The relevant statement is therefore not merely that an agent owns a credential, corresponds to a registered identity, or executes approved code. The statement of interest is whether a specific authorization request is supported by private attributes and contextual information that satisfy an applicable policy.
(6)
and a verifier accepts if: VerifyAuth(pp, x, π) = 1.
(7)
VerifyAuth denotes authorization-level proof verification. Intuitively, x captures what the verifier is allowed to know, while w captures what the prover must know but should not disclose. VerifyAuth invokes the verifier of the underlying ZKP system over the public statement x and proof π. Stateful checks, such as replay protection, are modeled separately. This proof system enables a verifier to establish that an authorization relation holds without learning the private witness, yielding the following conceptual separation: Identity Evidence ̸≡ Authorization Evidence ̸≡ Execution Evidence.
(8)
We use the term evidence object to denote the cryptographic, procedural, or runtime artifact presented to justify a security-relevant claim about an agent. In agentic systems, different evidence objects support different claims. Identity evidence supports claims about who or what an agent is. Delegation evidence supports claims about authority transferred from a principal to an agent. Authorization evidence supports claims about whether a concrete request satisfies a policy under a given context. Execution evidence supports claims about what action was actually executed at runtime. Audit evidence supports claims about historical traceability after execution. We refer to this missing object as authorization evidence: evidence that a concrete agent request, rather than merely an agent identity or delegated credential, satisfies an applicable policy under a given context. This paper makes three contributions. First, it introduces a preliminary formal abstraction of cryptographically verifiable agent authorization as a request-bound security relation. Second, it defines a compact set of candidate properties addressing soundness, principal binding, request binding, policy binding, and replay resistance. Third, it maps an existing zero-knowledge authorization prototype to the abstraction and uses it as evidence of constructive feasibility.
We formulate the following central hypothesis: H1 — Cryptographically Verifiable Agent Authorization Hypothesis. Authorization decisions for autonomous AI agents can be represented as cryptographically verifiable relations that jointly bind an agent principal, a concrete authorization request, an execution context and satisfaction of an applicable policy, while selectively preserving the confidentiality of private authorization attributes. We denote by RCV A the relation underlying Cryptographically Verifiable Authorization (CVA). At a high level, x encodes the public authorization statement (comprising the agent’s public identifier), a commitment to the requested action, a context commitment, a policy identifier, and freshness parameters; while w encodes the private witness, including the agent’s secret, private authorization attributes, and the preimages of the public commitments. We define Cryptographically Verifiable Authorization as the ability of a prover to produce evidence π showing that a public authorization statement x is supported by private witness data w that satify an authorization relation RCV A , without revealing w. 2
2. Related Work and Positioning — Zeroknowledge proofs have progressively moved from foundational interactive protocols [8] to practical noninteractive constructions suitable for real-world deployment. Groth16 [9] established the basis for efficient pairing-based non-interactive arguments; STARKs [10] removed trusted-setup requirements at the cost of larger proofs; Bulletproofs [11] provided efficient range proofs without trusted setup. Systematic surveys [12, 13] confirm the increasing maturity of ZKP frameworks and tooling, while applied work demonstrates their viability in distributed authentication contexts [14, 15, 16, 17]. In the agentic domain, DIAP [4] addresses decentralized agent identity and ownership via ZKP over a hybrid P2P stack. Huang et al. [6] investigate zero-trust identity architectures and fine-grained access control for agentic AI. Binding Agent ID [5] advances user-toagent-to-code binding with execution provenance. The Aegis Protocol [7] incorporates ZKP-based policy compliance into a broader agent security architecture combining decentralized identifiers and post-quantum cryptography. Adjacent work explores privacy-preserving audit of agent communications [18] and verifiable delegation in agent interaction protocols. These works establish the cryptographic feasibility of proving private statements without disclosure; however, the authorization object studied here is not a generic statement, but a request-specific relation involving principal, request, context, and policy. These systems demonstrate that agent identity, execution provenance, delegation, and policy compliance can be made verifiable. The remaining question addressed in this paper is whether authorization itself can be isolated as an independent cryptographic relation. The resulting landscape motivates an explicit separation among identity, delegation, policy compliance, audit, ZKP-based verification, and request-specific authorization, as summarized in Table 1. The intended gap is deliberately narrow: existing work substantially advances identity, delegation, policy compliance, and audit, whereas request-bound cryptographically verifiable authorization remains insufficiently characterized as an independent security abstraction. This work focuses specifically on the relation among principal, request, context, and policy. Table 1 reveals that while ZKP-based approaches have been applied to agent identity, code binding, policy compliance, and audit, no existing work explicitly models authorization as a request-bound cryptographically verifiable relation. This motivates the abstraction introduced in Section 3. Adjacent work by Prakash [19] introduces InvocationBound Capability Tokens for verifiable delegation across MCP and A2A, demonstrating sub-millisecond verification overhead in reference implementations evaluated in a real multi-agent deployment. While AIP advances the delegation and identity layers with cryptographic token chains, it does not model authorization as a request-bound relation with verifiable policy satisfaction and private witness; the two contributions address complementary layers of the agentic trust stack.
Furthermore, no existing work explicitly addresses the gap between authorization-request binding and runtime execution binding: the question of whether the action authorized at verification time is the same action subsequently executed. This structural observation, formalized in Subsection 4.5, is not explicitly addressed in current agentic security frameworks and motivates a distinct line of formal inquiry. 3. Preliminary Formal Model — 3.1. System and Request Model. We model an agentic authorization environment as a tuple: S = (A, G, T, R, P ),
(9)
where A is the set of autonomous agents, G the set of authorization gateways or verifiers, T the set of external tools or callable services, R the set of protected resources, and P the set of authorization policies. To refer to a specific protected resource, we write res ∈ R. Let λ denote the cryptographic security parameter. The notation {0, 1}λ denotes the set of bitstrings of length λ. An agent Ai ∈ A holds private key material denoted as sk: sk i ∈ {0, 1}λ , (10) and exposes a public identity commitment: id i = CommitID(sk i , ρi )
(11)
where CommitID denotes a randomized cryptographic commitment scheme for agent identity, sk i is the private secret of Ai , and ρi is the commitment randomness, with ρi ∈ {0, 1}λ . In standard cryptographic notation, this corresponds to a commitment of the form Com(m; r). This formulation [20] is consistent with privacy-preserving and anonymous authentication protocols, where commitments allow a prover to bind to secret information without disclosing it. A commitment-based identifier allows the model to represent agent binding without requiring direct disclosure of the underlying secret material. In the proof-of-concept implementation, this abstraction is instantiated in simplified form as id i = Poseidon(sk i ) [21], primarily for ZK-circuit efficiency. This provides principal binding under hash assumptions but does not realize the randomized hiding semantics of the general commitmentbased model; this distinction is acknowledged as a limitation. We define an authorization request as: qi = (id i , α, res, c, pid j , n, t)
(12)
where the tuple qi is designed to be minimal but sufficient: id i commits to the requesting agent Ai , α is the requested action, res ∈ R identifies the concrete protected resource, c, the execution concept, captures runtime-dependent attributes that may affect policy evaluation, n is a nonce, and t is a validity epoch or timestamp. We reserve P for the set of authorization policies. A concrete policy is denoted Pj ∈ P , following the same indexing convention as Ai ∈ A. The versioned 3
Table 1. Positioning of related work with respect to authorization-relevant security properties. Work
Identity
Delegation
Policy compliance
Audit
Preexecution authorization
ZKP
DIAP [4] Huang et al. [6] BAID [5] Aegis [7] zk-MCP [18] AIP [19] Proposed CVA
✓ ✓ ✓ ✓ – ✓ Principal binding, not full identity framework
– Partial – – – ✓ Orthogonal
– ✓ Partial ✓ Rule-oriented Attenuation ✓
– – – – ✓ Provenance –
– Partial Partial Partial – Partial ✓
✓ Partial ✓ ✓ ✓ ✗ ✓
policy identifier pid j = HP (policy_code j ∥ version j ) is a compact cryptographic reference to Pj , used in the public statement to bind the proof to a specific policy version without encoding the full policy in the circuit. Additional attributes such as risk scores or session identifiers may be incorporated into c without modifying the core model structure. An action may be decomposed as: α = (tool, operation, args),
tool ∈ T.
the authorization request, as defined in Equation (14). Similarly, hc = Hc (Encode(cpriv )) is a commitment to security-relevant contextual attributes, where Hc is a collision-resistant hash function applied to a canonical serialization of the private context. The inclusion of hc in the public statement extends the binding surface of the relation beyond the request itself to encompass runtime-dependent conditions (such as environment classification, resource state, or session attributes) that may affect policy evaluation. While hc is part of the formal model, its implementation is left open in the current proof-of-concept and identified as a priority for future implementation. The private witness is:
(13)
Where request data are sensitive, the public commitment is computed as: hq = Hq (Encode(domain, tool, operation, res, args)),
(14)
w = (sk i , ρi , attrs i , qpriv , cpriv )
where Encode denotes a deterministic canonical serialization function. We denote by: qpriv := (domain, tool, operation, res, args)
(17)
where attrs i encodes private authorization attributes not revealed to the verifier, qpriv denotes the private canonical request known by the prover, while hq is its public commitment. Similarly, cpriv denotes private contextual attributes, while hc is their public commitment. The value ρi is the randomness required to open the identity commitment id i . The separation between x and w captures the privacy objective of the model: the verifier observes the statement required for authorization, while sensitive attributes and preimages remain private.
(15)
the private canonical representation of the request committed in Equation (14); the execution context c is committed separately through hc (see Subsection 3.2), while the remaining fields of qi (id i , pid j , n, t) appear in the clear in the public statement. Canonical encoding is required to avoid ambiguity between semantically equivalent but byte-distinct requests. Without canonical encoding, two semantically equivalent requests may yield different commitments, while two differently serialized requests may create ambiguity about what was actually authorized. Throughout the paper, Hq , Hc , and HP denote domain-separated collision-resistant hash functions, or domain-separated invocations of the same underlying hash primitive. The subscript identifies the semantic domain of the commitment: request, context, or policy. The lowercase values hq , hc , and pid j denote the resulting public commitments or identifiers.
3.3. Core Authorization Relation. The preliminary CVA relation is defined as RCV A (x, w) = 1 if and only if the following constraints are jointly satisfied: CommitID(sk i , ρi ) = id i ,
(18)
Hq (Encode(qpriv )) = hq
(19)
Hc (Encode(cpriv )) = hc
(20)
and
3.2. Public Statement and Private Witness. The public statement is defined as:
where hc is the context commitment introduced in Equation (16) and
x = (id i , hq , hc , pid j , n, t).
Pj (attrs i , qpriv , cpriv ) = 1.
(16)
(21)
Here each policy Pj ∈ P is modeled as a deterministic predicate over (attrs i , qpriv , cpriv ), and Pj is the policy
As established in Subsection 3.1, hq = Hq (Encode(qpriv )) is the public commitment to 4
referenced by the identifier pid j contained in the public statement x. In compact form:
Authorization-Request Binding (see Subsection 4.3). Fourth, cross-policy transfer: the adversary attempts to present a proof generated under one policy identifier RCV A = BindPrincipal ∧ BindRequest as evidence under another policy identifier, addressed (22) by Policy Binding in Equation (31). Fifth, replay: the ∧ BindContext ∧ SatisfyPolicy. adversary reuses a previously accepted proof to obtain We define BindPrincipal as: a second authorization, addressed by Replay Resistance (see Subsection 4.4). The goal of this adversary model BindPrincipal := [ CommitID(sk i , ρi ) = id i ]. (23) is not to cover all failures of autonomous execution, but to isolate attacks that target authorization eviThe intended proof of knowledge is: dence itself. A complete symbolic adversary model for π = PoK{ (sk i , ρi , attrs i , qpriv , cpriv ) : RCV A (x, w) = 1 }. multi-agent authorization chains is left as future work. (24) 4. Candidate Security Properties — The followEquivalently, π proves knowledge of a witness w sating properties are intended to address the principal isfying RCV A (x, w) = 1. Each conjunct in RCV A attack vectors identified in the threat model of Subsecrules out a distinct class of transfer attack. Omittion 3.4: proof forgery without a valid witness, crossting BindPrincipal enables cross-principal reuse; omitprincipal proof transfer, cross-request proof transfer, ting BindRequest enables policy-satisfying proofs to cross-policy proof transfer, and proof reuse. Comauthorize unintended actions; omitting BindContext plete reductions of these properties to standard cryptoweakens context-dependent authorization; and omitting graphic assumptions, in particular the soundness and SatisfyPolicy decouples the proof from the authorizaknowledge-soundness of the underlying proof system tion decision itself. Their conjunction is the minimal and the binding property of CommitID, are left as part condition for request-specific authorization verifiability. of the future research agenda. The separation between This construction proves satisfaction of a committedauthorization-request binding and runtime execution request relation; it does not prove the internal reasoning binding in Subsection 4.5 is included as a structural or deliberative process of the agent: observation rather than a game-based property, since it identifies a limitation of the ZKP authorization layer Request Commitment ̸= Internal Agent Intent. (25) itself. Two further properties assessed in Table 2 are Freshness depends on external mutable state and is not stated as separate games: attribute privacy is intherefore separated from the stateless cryptographic herited directly from the zero-knowledge property of core: the underlying proof system, and context binding is captured structurally as the conjunct Equation (20) Accept(x, π) = VerifyAuth(pp, x, π) ∧ Fresh(n, t, N ) of RCV A , with its transfer-resistance form given in (26) Equation (36). where N is the set of previously consumed nonces 4.1. Authorization Soundness. Let Adv denote maintained by the gateway. a probabilistic polynomial-time adversary; the ad3.4. Threat Model. We consider a probabilistic versary should not be able to produce an accepted polynomial-time adversary Adv operating against the proof for a statement for which no valid witness exists. CVA authorization workflow. The adversary may obThe adversary wins the authorization soundness game serve, intercept, and replay authorization statements Gameauth-sound (λ) if it outputs (x⋆ , π ⋆ ) such that: Adv and proofs; substitute or forge public agent identifiers; modify or substitute request commitments; present VerifyAuth(pp, x⋆ , π ⋆ ) = 1 ∧ ∄ w : RCV A (x⋆ , w) = 1. proofs under policy contexts different from those for (27) which they were generated; and control unauthorized A secure construction requires: or partially authorized agents. The adversary cannot break the assumed cryptographic primitives, directly Advauth-sound (λ) ≤ negl(λ). (28) Adv obtain honest party secrets, or compromise the trusted authorization gateway. This bound follows from two assumptions. First, These capabilities identify five primary attack classes the underlying proof system must satisfy knowledgeagainst the proposed abstraction. First, proof forgery: soundness: an accepting proof for a statement should the adversary attempts to produce an accepting proof imply the existence of an extractable witness for the for a statement for which no valid witness exists, encoded relation. Second, the implemented circuit and addressed by Authorization Soundness (see Subsecverification metadata must correctly encode and bind tion 4.1). Second, cross-principal transfer: the adthe intended relation RCV A . Thus, an adversary that versary attempts to reuse a valid proof generated for wins the game in Equation (27) must either violate principal id i to authorize a request under a different knowledge-soundness of the proof system or exploit principal id k , addressed by Principal Binding (see Suba mismatch between the intended CVA relation and section 4.2). Third, cross-request transfer: the adits encoded implementation. A complete reduction, versary attempts to reuse a proof bound to request including explicit extractor and simulation arguments, qi to authorize a distinct request qi′ , addressed by is left for future work. 5
4.2. Principal Binding. We use Pr[ · ] to denote the probability of an event over the randomness of the adversary, the proof system, and the experiment. Let xi = (id i , hq , hc , pid j , n, t) and xk = (id k , hq , hc , pid j , n, t) with id i ̸= id k . A proof πi generated for principal id i must not verify under xk : Pr[ VerifyAuth(pp, xk , πi ) = 1 ] ≤ negl(λ).
4.4. Replay Resistance. Let N denote the consumed nonce set defined in Equation (26). Once a request with nonce n has been successfully accepted, the gateway updates its replay-control state as follows: N ← N ∪ {n},
(29)
The complete freshness predicate is defined as:
Principal binding relies on the binding property of CommitID and on the soundness of the proof system.
Fresh(n, t, N ) = 1 ⇔ (n ∈ / N )∧(tmin ≤ t ≤ tmax ) (38) Fresh(n, t, N ) = 0 ⇔ (n ∈ N ) ∨ (t < tmin )∨ (t > tmax ) (39) n ∈ N ⇒ Fresh(n, t, N ) = 0. (40)
4.3. Authorization-Request Binding. Let qi ̸= qi′ be two distinct requests whose private canonical components differ, with commitments hq = ′ Hq (Encode(qpriv )) and h′q = Hq (Encode(qpriv )). Let πq denote a proof generated for the statement xq containing hq , and xq′ the statement containing h′q . A proof bound to qi must not authorize qi′ : Pr[ VerifyAuth(pp, xq′ , πq ) = 1 ] ≤ negl(λ).
Equation (38) defines acceptance: a nonce is fresh if it has not been previously consumed and the timestamp falls within the authorized validity window, delimited by the gateway-defined bounds tmin and tmax . Equation (39) captures both replay via nonce reuse and replay via deferred presentation outside the validity window as rejection conditions. Subsequent reuse of n is therefore rejected, as in Equation (40). Equation (39) and Equation (40) are the explicit contrapositive forms of Equation (38), stated separately to make the rejection conditions directly enforceable at the gateway. Replay resistance is a property of the complete authorization workflow and depends on stateful external enforcement at the gateway. The consequence of Fresh(n, t, N ) = 0 is that the full acceptance predicate of Equation (26) evaluates to false, regardless of proof validity. The ZK proof binds the request to the public statement, while the gateway enforces single-use semantics through mutable nonce state and temporal validity checks. Note that gateway-side freshness is meaningful only because n and t are bound to the proof as components of the public statement x: a proof not bound to its nonce could be re-presented by an adversary under a fresh nonce n′ ∈ / N , voiding replay control. Statement binding of n and t is therefore a precondition of Subsection 4.4, not an optional design choice.
(30)
This property is central to the proposed abstraction: abstract policy satisfaction alone is insufficient if the authorization evidence can be detached from the specific request to which it applies. A related condition, which we term Policy Binding, establishes that a proof generated under policy version pid j must not verify as valid evidence under a distinct policy version pid k : pid j ̸= pid k ⇒ Pr[ VerifyAuth(pp, xpid k , πpid j ) = 1 ] ≤ negl(λ).
(31)
This property is enforced by including pid j in the public statement x and constraining the circuit to evaluate the policy identified by pid j as defined in Subsection 3.1. An analogous condition, which we term Context Binding, requires that a proof generated under one context commitment must not verify under a statement carrying a distinct context commitment. Let hc = Hc (Encode(cpriv ))
(37)
(32)
and h′c = Hc (Encode(c′priv )),
cpriv ̸= c′priv .
4.5. Authorization Binding Is Not Equivalent to Execution Binding. A valid proof establishes that a committed request satisfies the authorization relation:
(33)
Under collision resistance of Hc , cpriv = ̸ c′priv implies ′ hc ̸= hc . Let xc = (idi , hq , hc , pidj , n, t)
(34)
xc′ = (idi , hq , h′c , pidj , n, t).
(35)
VerifyAuth(pp, xq , π) = 1.
(41)
This does not imply that the runtime subsequently executes the same request. Formally:
and
VerifyAuth(pp, xq , π) = 1 ⇏ qexec = qauth
A proof πc generated for xc must not verify under xc′ : Pr VerifyAuth(pp, xc′ , πc ) = 1 ≤ negl(λ). (36)
(42)
where qauth denotes the request committed in the verified statement xq and qexec denotes the request actually executed by the runtime. Therefore:
This property relies on the collision resistance of Hc , canonical context encoding, and the correct inclusion of hc as a constrained public input of RCVA . Context Binding prevents substitution of the context commitment at authorization time; it does not, by itself, prevent context drift between authorization and subsequent execution, which is addressed separately as a TOCTOU limitation in Section 6.
Authorization Request Binding ̸≡ Runtime Execution Binding.
(43)
This gap is structural rather than incidental. A ZK circuit is evaluated at proof generation time over a committed representation of the intended request; it 6
has no access to the runtime state at execution time and cannot constrain what the agent subsequently does with the authorization it receives. Closing this gap requires a trust anchor that operates at execution time rather than at proof generation time. Establishing runtime consistency requires an additional trusted evidence mechanism, such as remote attestation, a trusted execution environment, or verifiable execution receipts, beyond the guarantees of the ZKP authorization relation. This constitutes an open problem and is identified as part of the research agenda.
bound to the proof as public inputs of the verified statement, as required by the replay precondition of Subsection 4.4. The corresponding private witness is: wP oC = (sk i , attrs i , plan)
(45)
where sk i is the private secret of the agent, attrs i denotes private authorization attributes, and plan represents the action sequence or request structure whose public commitment is hplan . These values remain private to the prover and are not disclosed to the gateway. The prototype relation is defined as:
5. Proof-of-Concept implementation — RP oC (xP oC , wP oC ) = 1 5.1. Scope. To assess the constructive feasibility of selected elements of the CVA abstraction, an executable zero-knowledge authorization prototype was developed and publicly presented prior to the formalization introduced in this paper [22]. This artifact is the experimental precursor from which the present hypothesis emerged. The prototype is not presented as a complete validation of the CVA abstraction. It demonstrates that selected bindings and private policy predicates can be instantiated in an executable pre-authorization workflow, providing constructive evidence of feasibility. The architecture follows the conceptual flow shown in Figure 1. The implementation employs the Groth16 zkSNARK construction [9] over the bn128 curve, with circuits written in Circom 2.x and proof generation via snarkjs. Groth16 was selected for its minimal proof size and constant verification time, properties favorable for gateway-side enforcement. The trusted setup requirement and the absence of post-quantum security are acknowledged limitations; alternative schemes are identified as part of the comparative evaluation agenda in Section 6. The gateway is implemented as a FastAPI service performing stateless proof verification and stateful replay control.
(46)
if the following three constraints are satisfied. First, the prover must demonstrate knowledge of the private secret corresponding to the public agent identifier. Instantiating Equation (18): Poseidon(sk i ) = id i
(47)
this constraint instantiates principal binding in the prototype. It ensures that a proof accepted for id i is generated by a prover that knows the corresponding private secret. Unlike the generalized model, where the agent identifier is represented through a randomized identity commitment, the current implementation uses a deterministic Poseidon-based identifier and therefore does not provide randomized commitment hiding semantics. Second, the proof must be bound to the plan that the gateway is expected to authorize. As a partial implementation of Equation (19): SHA256(plan) = hplan
(48)
this constraint provides request binding at the level of the committed plan. It prevents a proof generated for one plan from being reused for a different committed plan, assuming collision resistance of the hash function and canonical encoding of the plan. Third, the private authorization attributes and the committed plan must satisfy the policy encoded in the circuit. Instantiating Equation (21):
5.2. Prototype Relation. The proof-of-concept instantiates a restricted version of the general CVA relation introduced in Section 3. As noted in Subsection 3.1, the formal model uses a randomized commitment CommitID(sk i , ρi ), while the prototype instantiates a simplified Poseidon-based form for circuit efficiency. Therefore, the prototype should be interpreted as an implementation of principal binding and request binding, but not as a full realization of the generalized commitment-based model. The public statement verified by the gateway is defined as: xP oC = (id i , hplan , n, t) (44)
PP oC (attrs i , plan) = 1.
(49)
This condition represents the policy-satisfaction component of the prototype. The predicate PP oC is implemented as arithmetic constraints in the ZK circuit and therefore captures only the policy logic explicitly encoded at circuit generation time. Freshness and replay protection are enforced outside the circuit by the authorization gateway: Fresh(n, t, N ) = 1
(50)
where N is the gateway-maintained set of previously consumed nonces. This separation is intentional: proof verification is stateless, whereas replay resistance requires mutable enforcement state. Consequently, freshness is treated as a property of the complete authorization workflow rather than as a guarantee provided solely by the ZK circuit.
where id i denotes the public identifier of the agent, hplan is the public commitment to the plan or requested action sequence, n is a nonce, and t is the validity timestamp or epoch. This public statement contains only the information required for the verifier to bind the proof to a specific agent, a specific committed plan, and a freshness window; in particular, n and t are 7
Figure 1. Proof-of-concept authorization workflow. The agent constructs a private witness and generates a proof via the ZK circuit. The gateway performs stateless proof verification and stateful freshness control before issuing an authorization decision.
Second, the correctness of a proof must not be confused with the normative correctness of the encoded policy. If the implemented relation RCV A does not faithfully encode the intended organizational policy Pintended (that is, if RCV A (x, w) = 1 as defined in Equation (4) does not imply Pintended (attrs i , qpriv , cpriv ) = 1) ,then a valid proof may correspond to an incorrectly authorized decision. Policy governance, versioning via pid j , circuit governance, and verification-key distribution therefore constitute first-class security concerns orthogonal to the cryptographic guarantees of the proof system. Third, dynamic execution introduces a time-ofcheck-to-time-of-use problem. If verification occurs at time tv and execution at te > tv , the relevant context may change: ctv ̸= cte . (53)
In compact form, the proof-of-concept instantiates: RP oC =BindPrincipalPoseidon ∧ BindPlanSHA256 ∧ SatisfyPolicyCircuit
(51)
with replay resistance enforced externally by the gateway as defined in Equation (38) and Equation (39). The PoC therefore supports the constructive plausibility of principal binding, plan-level request binding, and private policy satisfaction, while leaving full context binding and runtime execution binding outside the implemented scope. The prototype should therefore be read as an executable witness of the abstraction’s feasibility, not as an empirical demonstration that the abstraction is complete. 5.3. Property Coverage Assessment. The conservative characterization is intentional. The purpose of Table 2 is to expose the distance between the preliminary formal model and the current artifact rather than to overstate prototype coverage.
Let Authorized(q, c) denote the predicate that holds when request q is authorized under context c; formally, when Accept(xq , π) = 1 for a proof π generated under context c, as defined in Equation (26). Consequently:
5.4. Preliminary Validation Strategy. Propertyoriented validation derives test cases directly from the candidate properties. Representative cases include: (i) a valid principal issuing a policy-compliant request; (ii) an invalid agent secret; (iii) substitution of the public identity commitment; (iv) modification of the request hash; (v) private attributes failing the encoded policy predicate; (vi) reuse of a previously consumed nonce; and (vii) tampering with public signals. These cases provide structured coverage of the instantiated properties but do not constitute complete empirical security evaluation against arbitrary adversaries.
Authorized(q, ctv ) = 1 ⇏ Authorized(q, cte ) = 1. (54) Fourth, a structural observation concerns multiagent delegation chains. The present model defines the CVA relation for a single agent-gateway interaction, where a prover Ai generates a proof for a single authorization request qi . In practice, autonomous agents increasingly operate in orchestrated architectures where Ai may delegate a subtask to another agent Ak , which may in turn delegate further. In such chains, the authorization question becomes compositional: Ak must not only prove that its local request qk satisfies a CVA relation, but also that the delegation from Ai to Ak preserves, constrains, or attenuates the authorization scope granted upstream. The current conjuncts of RCV A in Equation (22), including BindPrincipal, BindRequest, and SatisfyPolicy, remain necessary but are not sufficient for multi-hop authorization soundness. A proof that Ak satisfies a local policy does not by itself establish that Ak was authorized to act under the scope delegated by Ai , or that scope has not been expanded across hops. Addressing this gap would require an additional delegation-binding component, such as BindDelegationScope, together with either (i) recursive proof composition -in which each hop proves that it extends and constrains the previous authorization state- or (ii) a delegation-aware witness structure encoding the relevant authorization chain. We leave the formal characterization of compositional
6. Discussion and Research Agenda — The purpose of the preliminary model is not only to propose a construction, but also to identify where the guarantees provided by ZKP-based authorization end. The preliminary model supports four principal observations. First, the separation among binding layers: Identity Binding ̸≡ Authorization Request Binding ̸≡Runtime Execution Binding. (52) A system may correctly authenticate an agent yet fail to bind authorization evidence to a specific request. It may likewise bind evidence to a request without guaranteeing that the same request is executed at runtime. These are structurally distinct security properties requiring separate mechanisms. 8
Table 2. Mapping between formal candidate properties and prototype mechanisms. Property
Prototype mechanism
Status
Authorization soundness
Circuit constraints and SNARK soundness assumptions Agent secret to deterministic Poseidonderived identifier Plan/action commitment via SHA-256
Partial
Principal binding Request binding Policy binding Replay resistance Attribute privacy
Fixed circuit/policy relation; no explicit pid j public input in the current prototype Nonce and external gateway state ZK witness under Groth16 assumptions
Context binding Runtime execution binding
No explicit context commitment No trusted execution evidence
CVA for multi-agent chains as a primary direction for future work. These four observations directly motivate the research questions that structure the future empirical and formal agenda:
Implemented Implemented for plan-level binding; partial relative to full CVA request binding Partial / not fully implemented Implemented externally Implemented under proof-system assumptions Open Open
authorization frequency may improve latency, but it increases the importance of binding the authorized plan to subsequent execution. These observations suggest that CVA should be evaluated along two separate axes: cryptographic validity of the authorization evidence, and operational consistency between authorization and execution. The first can be studied through proof-system soundness, binding properties, and circuit correctness; the second requires additional runtime evidence mechanisms and cannot be obtained from the authorization proof alone.
RQ1 — Necessary Bindings. Which dimensions must be cryptographically bound to prevent proof transfer across principals, requests, contexts, policies, and execution domains? In particular, the present model includes context binding through hc as a formal conjunct in RCV A , but its implementation and the characterization of which contextual attributes are necessary and sufficient for policy-relevant binding remain open. RQ1 subsumes this as a central sub-question.
7. Limitations — We explicitly acknowledge the following limitations:
RQ2 — Representable Policies. Which classes of agent authorization policies can be efficiently represented as arithmetic ZK relations under practical circuit complexity constraints?
1. The formal model is preliminary; complete security reductions for the proposed candidate properties to standard cryptographic assumptions remain as future work.
RQ3 — Operational Viability. What overhead is introduced by request-bound ZKP authorization under different proof systems and agent workload profiles?
2. The prototype has not been subjected to independent cryptographic circuit audit.
Preliminary evidence from the proof-of-concept suggests that, for the selected Groth16 implementation [9], gateway-side verification remains effectively constant with respect to circuit constraint count and can be performed with very low latency. In contrast, proof generation scales with the number of arithmetic constraints and is therefore expected to dominate end-to-end authorization latency as policy expressiveness increases. Operational viability consequently depends not only on the selected proof system, but also on the authorization frequency of the deployment model. A low-frequency model, in which a proof is generated once per task plan and verified once at the gateway, presents a fundamentally different latency budget from a high-frequency model in which each tool invocation triggers an independent authorization cycle. RQ3 should therefore be evaluated across at least three axes: proof-system selection, circuit complexity as a function of policy expressiveness, and authorization frequency as a function of the agent workload profile. This distinction also reinforces the separation between authorization evidence and runtime execution evidence: reducing
3. Groth16 requires a trusted setup ceremony; the resulting common reference string constitutes an external trust assumption. The system is additionally not post-quantum secure under current assumptions. 4. The encoded policy language is constrained to static arithmetic circuits; dynamic or procedural policies are not representable without circuit recompilation. 5. Context binding is included in the formal model through Hc (Encode(cpriv )) = hc , but is not implemented in the current prototype. 6. Runtime execution binding is an open problem not addressed by the ZKP authorization layer alone, as formalized in Equation (41) and Equation (42). 7. No comparative empirical benchmark across proof systems has been conducted. 8. No multi-agent or multi-principal delegation chain has been evaluated. 9
9. The authorization gateway is partially trusted; its compromise is outside the threat model of the core cryptographic construction.
References — [1] V. Gupta, “The looming authorization crisis: Why traditional IAM fails agentic AI,” ISACA Industry News, Dec. 2025, ISACA.
8. Conclusion — This paper argues that authorization for autonomous AI agents should be studied as a cryptographically verifiable security relation, rather than solely as a consequence of authenticated identity or delegated credentials. We hypothesize that a meaningful class of authorization decisions can be represented through relations jointly binding an agent principal, a concrete authorization request, an execution context, and the satisfaction of an applicable policy, while selectively preserving private authorization attributes. Table 1, discussed in Section 2, positions the proposed abstraction relative to existing work: while prior contributions advance identity, delegation, policy compliance, and audit, the CVA abstraction targets the orthogonal property of request-bound verifiable authorization, which remains uncharacterized as an independent security relation in the surveyed literature. To support this hypothesis, we introduced a preliminary formal model, defined a compact set of candidate security properties, and mapped an executable zeroknowledge proof-of-concept to selected elements of the abstraction. The artifact is presented as constructive evidence of feasibility rather than complete formal or empirical validation. The central conclusion is the explicit separation (as we defined in the Equation (52)):
[2] D. Hardt, “The OAuth 2.0 authorization framework,” Internet Engineering Task Force, Request for Comments 6749, 2012, doi: 10.17487/RFC6749. [3] T. South, S. Nagabhushanaradhya, A. Dissanayaka, S. Cecchetti, G. Fletcher, V. Lu, A. Pietropaolo, D. H. Saxe, J. Lombardo, A. M. Shivalingaiah, S. Bounev, A. Keisner, A. Kesselman, Z. Proser, G. Fahs, A. Bunyea, B. Moskowitz, A. Tulshibagwale, D. Greenwood, J. Pei, and A. Pentland, “Identity management for agentic AI: The new frontier of authorization, authentication, and security for an AI agent world,” OpenID Foundation, Whitepaper, 2025, OpenID Foundation. [4] Y. Liu, W. Xing, Y. Zhou, G. Chang, C. Lin, and M. Han, “DIAP: A decentralized agent identity protocol with zero-knowledge proofs and a hybrid P2P stack,” arXiv preprint, 2025, arXiv:2511.11619. [5] Z. Lin, S. Zhang, G. Liao, D. Tao, and T. Wang, “Binding agent ID: Unleashing the power of AI agents with accountability and credibility,” arXiv preprint, 2025, arXiv:2512.17538. [6] K. Huang, V. S. Narajala, J. Yeoh, J. Ross, M. Lambe, R. Raskar, Y. Harkati, J. Huang, I. Habler, and C. Hughes, “A novel zero-trust identity framework for agentic AI: Decentralized authentication and finegrained access control,” in 2026 IEEE International Conference on Artificial Intelligence and eXtended and Virtual Reality, Data, Knowledge Engineering (AIxDKE), 2026, pp. 98–101, IEEE Xplore.
Identity Binding ̸≡ Authorization Request Binding
[7] S. T. R. Adapala and Y. R. Alugubelly, “The aegis protocol: A foundational security framework for autonomous AI agents,” arXiv preprint, 2025, arXiv:2508.19267.
̸≡Runtime Execution Binding. This distinction clarifies both the contribution and the limits of zero-knowledge authorization: a proof may establish that a committed request satisfies an encoded policy, but cannot by itself establish that the same request was subsequently executed. The resulting abstraction provides a falsifiable basis for future formal security analysis, comparative evaluation across proof systems, and integration with trusted runtime execution evidence. Beyond the specific research questions identified in Section 6, the CVA abstraction suggests a broader reorientation of how authorization is studied in agentic systems: not as a configuration problem solved at deployment time, but as a per-request cryptographic property that must be established, verified, and composed across agent interactions. As autonomous agents become infrastructure (invoking tools, delegating tasks, and acting upon protected resources at scale), the gap between authenticated identity and verified authorization is likely to widen. Closing it requires not only formal foundations of the kind proposed here, but also a broader effort to develop authorization evidence as a first-class security primitive alongside identity, delegation, and runtime execution evidence.
[8] S. Goldwasser, S. Micali, and C. Rackoff, “The knowledge complexity of interactive proof-systems,” in Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali. Association for Computing Machinery, 2019, pp. 203–225, doi: 10.1145/3335741.3335750. [9] J. Groth, “On the size of pairing-based noninteractive arguments,” in Advances in Cryptology— EUROCRYPT 2016, 2016, pp. 305–326, doi: 10.1007/ 978-3-662-49896-5_11. [10] E. Ben-Sasson, I. Bentov, Y. Horesh, and M. Riabzev, “Scalable, transparent, and post-quantum secure computational integrity,” Cryptology ePrint Archive, Paper 2018/046, 2018, ePrint:2018/046. [11] B. Bünz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell, “Bulletproofs: Short proofs for confidential transactions and more,” in 2018 IEEE Symposium on Security and Privacy (SP), 2018, pp. 315–334, doi: 10.1109/SP.2018.00020. [12] N. Sheybani, A. Ahmed, M. Kinsy, and F. Koushanfar, “Zero-knowledge proof frameworks: A systematic survey,” arXiv preprint, 2025, arXiv:2502.07063. [13] S. Gupta, “Zero-knowledge proofs for privacypreserving systems: A survey across blockchain, identity, and beyond,” Engineering and Technology Journal, vol. 10, no. 7, pp. 5755–5761, 2025, doi: 10.47191/etj/ v10i07.23.
10
[14] A. Nait Cherif, Y. Achir, M. Youssfi, M. Elgarej, and O. Bouattane, “Zero-knowledge proofs and OAuth 2.0 for anonymity and security in distributed systems,” E3S Web of Conferences, vol. 469, 2023, art. no. 00085. doi: 10.1051/e3sconf/202346900085. [15] S. Mo, W. Feng, M. Huang, S. Feng, Z. Wang, and Y. Li, “Two-factor authentication for intellectual property transactions based on improved zero-knowledge proof,” Scientific Reports, vol. 15, no. 1, 2025, art. no. 5974. doi: 10.1038/s41598-025-89597-7. [16] J. Xiang, O. Salem, A. Mehaoua, S. Wicha, and P. Sureephong, “Secure blockchain-based single signon with zero-knowledge proof authentication,” in 2025 Global Information Infrastructure and Networking Symposium (GIIS), 2025, pp. 1–6, IEEE Xplore. [17] S. Gopal, “Building a robust OAuth token based API security: A high level overview,” arXiv preprint, 2025, arXiv:2507.16870. [18] G. Jing and H. Qi, “Zero-knowledge audit for Internet of Agents: Privacy-preserving communication verification with Model Context Protocol,” arXiv preprint, 2025, arXiv:2512.14737. [19] S. Prakash, “AIP: Agent identity protocol for verifiable delegation across MCP and A2A,” arXiv preprint, 2026, arXiv:2603.24775. [20] T. P. Pedersen, “Non-interactive and informationtheoretic secure verifiable secret sharing,” in Advances in Cryptology—CRYPTO ’91, 1992, pp. 129–140, doi: 10.1007/3-540-46766-1_9. [21] L. Grassi, D. Khovratovich, C. Rechberger, A. Roy, and M. Schofnegger, “Poseidon: A new hash function for zero-knowledge proof systems,” in 30th USENIX Security Symposium (USENIX Security 21), 2021, pp. 519–535, USENIX. [22] M. Llambí, “zk-auth-agent-demo: Prototype for zeroknowledge-based authorization in agentic systems,” GitHub repository, 2026, GitHub.
† Corresponding author: [email protected]
11