arXiv:2606.15822v1 [cs.AI] 14 Jun 2026
TrustedARI: Towards Trust-Native Agentic Routing Infrastructure for Agentic AI
Qi Li Tsinghua University [email protected]
Zhenhua Zou Tsinghua University [email protected]
Shuo Li Tsinghua University [email protected]
Mingwei Xu Tsinghua University [email protected]
Zhuotao Liu ∗ Tsinghua University [email protected]
Abstract AI agents increasingly access external models, tools, and services through Agentic Routing Infrastructure (ARI) to manage the overhead of heterogeneous interfaces and fragmented subscriptions. Yet, the architecture of ARI introduces fundamental trust risks: it obtains plaintext access to agent queries and service responses, while leaving agents unable to verify that their queries are routed to intended service providers or that requests and responses remain untampered. To address this problem, we present TrustedARI, the first trust-native agentic routing infrastructure for agentic AI. Architecturally, TrustedARI is built upon three core innovations: (i) an ARI-adapted three-party TLS handshake that enables the agent and ARI to jointly authenticate the service provider through role-specific distribution of TLS key materials; (ii) a privacy-preserving query-construction protocol that allows the agent and ARI to collaboratively construct well-formed queries without exposing their respective private inputs; and (iii) a verifiable billing protocol that supports fair usage-based settlement while preserving the integrity and confidentiality of service responses. We implemented and extensively evaluated a prototype of TrustedARI to validate its performance. Experiments confirm that TrustedARI is highly efficient: our ARIadapted handshake protocol reduces communication overhead by 39.34% compared to the existing three-party TLS handshake. Furthermore, the privacy-preserving query-construction protocol imposes negligible overhead–averaging 0.19 seconds in computation time and 0.58 MB in communication costs–while the verifiable billing protocol speeds up proof generation by 28.20×. Crucially, TrustedARI is readily deployable without any modification to the service providers.
1
Introduction
Artificial Intelligence (AI) agents are increasingly deployed as autonomous systems that execute complex, multi-step workflows via external models, tools, and services [40]. However, direct integration between agents and individual service providers imposes non-trivial deployment overhead, such as highly heterogeneous interfaces, long-tailed API maintenance [33], and regional network or policy restrictions. Economically, fragmented access to diverse models and tools imposes significant ∗ Corresponding author.
Preprint.
Agent A
ARI R API-Key
Q = "Analyze confidential M&A memo"
Service Provider S
Privacy Leakage HTTPS Request HTTPS Response R = {"Deal: $3.2B"} Endpoint Misbinding
R' = {"Deal: $1.2B"} Integrity Failure
Figure 1: The architecture of ARI and its security risks. subscription costs on individual users for occasional task execution. To avoid these engineering frictions, emerging AI ecosystems increasingly rely on an intermediate layer that we refer to as Agentic Routing Infrastructure (ARI), which primarily manifests in two paradigms: LLM API Routing (e.g., OpenRouter [35], LiteLLM [1]) to facilitate model invocation and Agent Tool Routing (e.g., Pipedream [2], Zapier [3]) for connecting various web services through the unified interfaces such as Model Context Protocol (MCP) [8]. Architecturally, ARI functions as an intermediary infrastructure positioned between the agent and service providers to abstract downstream service interfaces, assemble and forward client requests, and establish a consolidated, usage-based billing pipeline. In a typical deployment, ARI holds the service-access metadata (e.g., API keys, prepaid credits) required to invoke these external service capabilities and charges agents for mediated calls. Given a target service (e.g., an LLM service or a web tool), the agent sends the request to ARI, which translates it into the service-specific invocation request and forwards it to the corresponding service provider. After receiving the provider’s result, ARI processes and returns the response to the agent. Despite this convenience, ARI introduces two fundamental trust issues: privacy leakage [52, 48] and the lack of end-to-end integrity guarantees [31]. Figure 1 illustrates these risks using LLM API Routing as an example. ARI receives the complete agent request, constructs a separate LLM-facing request using ARI-held credentials, and relays the LLM’s response. Thus, ARI observes both the agent query and the model output in plaintext. Second, the agent lacks a reliable mechanism to verify the service integrity. On the one hand, the agent cannot verify that ARI invokes the intended LLM provider, i.e., a request intended for a premium model may be forwarded to a different provider offering lower-tier model services. On the other hand, the agent also cannot confirm that the query is forwarded unchanged or that the response is returned unchanged by the ARI. The same privacy and integrity issues persist in the Agent Tool Routing paradigm, where the downstream endpoints are general web services instead of LLMs. To address these problems, we introduce TrustedARI, a trust-native agentic routing infrastructure for agentic AI. The key idea of TrustedARI is to decouple ARI’s participation in constructing and relaying a service request from its capability to observe or unilaterally control the invocation. To this end, TrustedARI leverages secure multi-party computation to enable the agent and the ARI to execute jointly as a “virtual client”, establishing a standard Transport Layer Security (TLS) session with the service provider, as illustrated in Figure 2. This joint execution securely encrypts the jointlycomputed requests to guarantee privacy, while yielding cryptographic evidence directly tied to the downstream service to ensure end-to-end integrity. The design of TrustedARI draws inspiration from TLS-oracles [50, 29, 44, 11, 39]. However, directly applying existing TLS-oracles to the ARI setting is infeasible, as the unique trust model and operational requirements of agentic routing introduce three fundamental challenges that TrustedARI resolves with dedicated protocol designs. First, unlike prior TLS-oracle settings, where one party provides private inputs and receives the plaintext payloads, the ARI setting has a fundamentally different interaction semantic. First, both the agent and ARI contribute private information to the query. Second, only one party (i.e., the agent) is allowed to received the authenticated and encrypted responses, while the other party (i.e., the ARI) is interested to verify certain billing-relevant data from the encrypted response. To realize this interaction semantic, TrustedARI introduces an ARI-adapted Three-party Handshake (§ 4) protocol, which distributes key material across protocol stages to enforce each party’s intended view. Handshake secrets are released to the agent so it can independently verify the identities of service providers to prevent mis-routing. The client application key is then secret-shared between both parties,
2
Agent A
ARI R
Service Provider S
Private Public Inputs ℇ" Template 𝒯
Private Inputs ℇ!
ARI-adapted Three-party TLS Handshake § 4
" , 𝜎! ) TLS (Q
Privacy-Preserving QueryConstruction Protocol § 5 Q = (𝒯, ℇ! , ℇ" )
", 𝜎" ) TLS (R
Verifiable Billing Protocol § 6
Figure 2: Overview of TrustedARI. allowing them to collaboratively construct encrypted requests. The server application key is first derived in secret-shared form to bind ARI to the session, and ARI later releases its share to the agent, enabling the agent to decrypt the full response while limiting ARI’s visibility only to billing-related fields. This dedicated key distribution not only fulfills the aforementioned interaction sematic, but also eliminates much of the expensive multiparty computation and zero-knowledge proofs required by existing TLS oracles [11]. Second, ARI-mediated requests encompass highly fragmented private inputs from both the agent (e.g., user prompts) and ARI (e.g., API keys), making it challenging to securely assemble a valid request without revealing any content-level or structure-level information. To address this problem, TrustedARI designs a privacy-preserving query-construction protocol (§ 5) that models ARImediated invocation as secure template instantiation. A public template, agreed upon by the agent and ARI, defines the request syntax and the ownership of different fields in the request. During template instantiation, the agent and ARI privately compute and assemble the ownership-tagged segments from their respective private inputs, while hiding both private field values and structural information (i.e., the length of a field in the query). Finally, leveraging the secret-shared TLS client-side application key, the agent and ARI derive the TLS-encrypted records of the assembled and well-structured requests that can be natively processed by the service provider. Third, ARI’s usage-based settlement becomes non-trivial given the confidentiality and integrity guarantees of responses. Specifically, under our key schedule, the agent obtains the complete TLSauthenticated response, while ARI observes only encrypted response records. Consequently, ARI cannot directly inspect billing-relevant fields (e.g., the token_usage field) embedded in the response, breaking its usage-based settlement model. To support fair settlement under the confidentiality/integrity guarantees, TrustedARI designs a verifiable billing protocol (§ 6). The protocol requires the agent to report the pre-declared billing-relevant fields and provide a zero-knowledge proof that these values are faithfully extracted from the TLS-authenticated response. TrustedARI substantially reduces proving cost by designing a ZKP-friendly circuit that attests only a small response window containing the billing fields, rather than the entire response packet [50, 6]. Contribution. The main contribution of this paper is the design, implementation and evaluation of TrustedARI, the first trust-native agentic routing infrastructure for agentic AI. We provide formal specifications of our protocols with rigorous security proofs. We implement a prototype of TrustedARI in approximately 9000 lines of C++ and 3000 lines of Go code, and perform extensive evaluations. Our evaluation confirms that TrustedARI is highly efficient compared to baselines constructed from existing approaches [11, 50, 22, 6]. Specifically, the ARI-adapted handshake reduces the connection setup latency to service providers by up to 50.47% compared to baselines, while cutting communication overhead by 39.34%. Meanwhile, the privacy-preserving query-construction protocol introduces minimal overhead, adding only 0.19 seconds (14.29%) in computation time and 0.58 MB (1.36%) in communication costs. Furthermore, the verifiable billing protocol achieves a 28.20× speedup in proof generation with a 33.26× reduction in circuit constraints. Crucially, TrustedARI is readily deployable without any modification to the service providers.
2
Preliminaries
Transport Layer Security (TLS) 1.3. As the foundation for secure communication, TLS ensures the authentication of service providers and the confidentiality and integrity of data transmission. 3
We focus on TLS 1.3 [38] because its cryptographic design—also adopted by the now-ubiquitous QUIC protocol [25]—has been reported to secure over 96% of web traffic [13]. Structurally, TLS 1.3 establishes keys via a handshake layer and protects application data using an AEAD scheme FAEAD in the record layer. We adopt the TLS 1.3 notation from Dowling et al. [15] in the paper. Secure Multiparty Computation (MPC) on Secret-Shared Data. TrustedARI builds on standard two-party computation (2PC) primitives, where intermediate values are represented as secret shares held by the agent and the ARI. We employ additive secret sharing over Z2k , where x = ⟨x⟩0 + ⟨x⟩1 (mod 2k ), and bitwise (XOR) sharing for k-bit strings, where x = ⟨x⟩0 ⊕ ⟨x⟩1 . Share conversion primitives, FA2B and FB2A , facilitate transitions between these domains. We denote shared values as ⟨x⟩, or as xA and xR for shares held by the agent and ARI when describing TLS cryptographic secrets. Our backend supports standard arithmetic, Boolean, and control-flow primitives (e.g., comparison and two-way multiplexer (FMUX2 ) [37]). Garbled Circuit (GC). For bitwise-heavy operations, we employ Yao’s garbled circuits [46, 47]. To ensure composability with the secret-sharing framework, we adopt an output-masking technique: the evaluator provides a random mask r, and the circuit computes y ⊕ r (or y + r (mod 2k )). The parties thus obtain XOR (or additive) shares of the actual result y without revealing the plaintext output to either party. For brevity, we treat GC as taking secret-shared inputs and producing secret-shared outputs, and omit this masking detail in the protocol description. Oblivious Transfers (OT). We use 1-out-of-2 oblivious transfer as a core building block. In OT, the sender holds (m0 , m1 ), the receiver chooses b ∈ {0, 1} and learns mb , while the sender learns nothing about b and the receiver learns nothing about m1−b . To reduce cost, we use IKNP OT extension [24] to amortize a small number of base OTs into many efficient OTs. Zero-knowledge Proofs. We employ zero-knowledge arguments of knowledge (ZK-AoK) to prove statements regarding an NP relation R without revealing the witness w. Formally, for a public input x and witness w such that (x, w) ∈ R, a prover P convinces a verifier V of the statement’s validity. The protocol satisfies completeness, zero-knowledge, and knowledge soundness, which ensures that any prover accepted with non-negligible probability can be used to extract a valid witness. See formal definitions in Appendix A. In our system, we instantiate the proving system with Plonk [20], a widely adopted NIZK construction.
3
Problem Statement
In this section, we introduce the ideal functionality of TrustedARI (i.e., Fsys , as shown in Functionality 1) to formally capture its input setting, computation goal, threat model, and privacy guarantee. There are three participating entities: the agent (A), the ARI (R), and the downstream service provider (S). Prior to protocol execution, the agent and ARI agree on a designated service provider and invocation specification, which together fix a public query template T and a billing-related response field selector φ. Structurally, T defines the public skeleton layout, field formatting constraints, and padding boundaries of the query request. Formally, the public query template is defined as a sequence of segment descriptors T = [τ1 , . . . , τL ], where each descriptor τi = (θi , hi ) specifies the segment category and ownership θi and its public padded length hi . The template T is public to both parties in advance, whereas the specific content populated within the variable slots represents private inputs. Under this setting, the agent and ARI provide their respective indexed entry sets (i.e., field contents) EA and ER . Each entry is a pair (i, s̃, g), where i identifies the segment position τi in the template and s̃ is the content string padded to the public length hi , and g is the true content length. The padding hides the true length of each party’s private content from the other party during secure assembly. The indices that appear in EA or ER are determined by the segment ownership encoded in θi . These entries correspond to agent-side query parameters or ARI-side service-access metadata, depending on the downstream service specification. The service provider is modeled as a standard TLS-protected external service; we only model its TLS transcript interface and omit its service-specific internal logic. The lifecycle of Fsys proceeds sequentially across three phases: handshake, query, and response. We use sid to denote a session identifier that links messages across these phases within the same service invocation. At the handshake stage, ARI initiates the session by submitting a proposed binding (sid, idS ) to Fsys , where sid identifies the invocation instance and idS denotes the target 4
Functionality Fsys interacts with A, R and S Input. A and R hold their respective indexed padded field contents EA and ER . A and R agree on a target service provider S, which fixes a public query template T and a billing-related field selector φ. S is modeled as a standard TLS server. Handshake: • Upon receiving (sid, idS ) from R, Fsys sends (sid, idS ) to A. • A independently validates that the session is bound to the agreed service provider S; if it fails, Fsys outputs ⊥ and aborts. Otherwise, Fsys records (sid, idS ) binding. Query: • Upon receiving EA from A and ER from R, Fsys computes Q ← Assemble(T , EA , ER ). • Fsys outputs the TLS-protected query transcript (sid, Q̂, σQ ) to A and R; R forwards (sid, Q̂, σQ ) to S. Response: • Upon receiving a TLS-protected response transcript (sid, R̂, σR ) from S, Fsys verifies its correctness; if it fails, Fsys outputs ⊥ and aborts. • Otherwise, Fsys forwards (sid, R̂, σR ) to both A and R, and outputs the plaintext response (sid, R) only to A. • Upon A submitting a declared billing value v, Fsys outputs (v, 1) to R if R[φ] = v, and (v, 0) otherwise.
Functionality 1: Ideal Functionality Fsys . service provider. Fsys forwards this proposed binding to the agent for independent validation. The agent checks whether idS matches the service provider agreed upon with ARI. If the check fails, Fsys outputs ⊥ and aborts; otherwise, Fsys records the binding (sid, idS ) for subsequent query and response processing. At the query stage, after receiving EA from the agent and ER from ARI, the procedure Assemble instantiates the template by truncating each padded content s̃ to its true length g and placing the recovered value into segment i, producing the plaintext query Q. Then, Fsys computes the TLSauthenticated query transcript (sid, Q̂, σQ ) for Q and outputs it to both the agent and ARI. Finally, the ARI forwards (sid, Q̂, σQ ) to the service provider. At the response stage, the service provider returns a TLS response transcript (sid, R̂, σR ). Then, Fsys validates its correctness. If the validation fails, Fsys outputs ⊥ and aborts. Otherwise, Fsys forwards (sid, R̂, σR ) to both parties and outputs the plaintext response (sid, R) only to the agent. Finally, when the agent submits the billing-relevant value v, Fsys checks whether R[φ] = v. If the check passes, Fsys outputs (v, 1) to the ARI; otherwise, it outputs (v, 0). Threat Model. In TrustedARI, we assume that the downstream service providers (e.g., LLM providers like OpenAI or tooling providers like GitHub) are honest. Attacks originating from these service providers (e.g., tool poisoning attacks [42], indirect prompt injection [12], and tool output attacks [52]) are therefore outside the scope of this work. We model both the agent and ARI as semi-honest but curious: they will not deviate arbitrarily from the protocol, but may try to infer each other’s private information or selfishly reap more economic benefits by choosing well-formed but self-serving input values at the protocol interfaces. Specifically, a self-interested agent may try to infer ARI’s private inputs, such as API keys, or reduce its payment by under-reporting token usage or disputing legitimate charges. Meanwhile, a self-interested ARI may try to monetize sensitive agent data by learning private requests or prompts, increase profit by routing requests to unintended lower-tier service providers, or exaggerate usage for overcharging. Essentially, TrustedARI follows a “trust-but-verify” paradigm. The agent verifies ARI’s routing behavior by authenticating the intended service provider and checking that the returned responses are authentic. Meanwhile, ARI verifies agent-side metering through the verifiable billing protocol, in which the agent provides a zero-knowledge proof that the reported billing fields are faithfully extracted from the encrypted response returned by the service provider. In §8, we discuss how TrustedARI can be extended toward a malicious-security model where the participants can arbitrarily deviate from the protocol. Private Data. The private data includes: (i) the agent-side field contents EA and the ARI-side field contents ER used for query construction; (ii) the plaintext response R released only to the agent. Additionally, all protocol-internal states computed from the aforementioned private data, including secret-shared intermediate values, must be kept secret throughout the process.
5
Public Data. The public data includes: (i) the session identifier sid, the target service provider idS , the query template T , and the billing-related field selector φ; (ii) the TLS-authenticate query and response transcripts (sid, Q̂, σQ ) and (sid, R̂, σR ); (iii) the declared billing value v and the verification result indicating whether R[φ] = v.
4
ARI-Adapted Three-party Handshake
Before the agent and ARI interact with a service provider, TrustedARI first performs a one-time connection setup that binds the interaction to the intended provider and establishes a channel to be reused across subsequent ARI-mediated invocations. We instantiate this setup as an ARI-adapted three-party TLS handshake, which allows the agent and ARI to jointly establish a standard TLS connection with the intended service provider while realizing ARI’s role-specific interaction semantics. Specifically, the agent and ARI jointly emulate a distributed “virtual TLS client” and, using secure multiparty computation, complete the handshake with the service provider without requiring any modification to the provider-side TLS implementation. During this handshake, TrustedARI distributes the derived TLS key material across protocol stages to align each party’s cryptographic capabilities with its role in ARI-mediated invocations. As a result, the agent can detect misrouting to unintended service providers, the agent and ARI can collaboratively construct service requests, and the agent ultimately obtains the complete provider response while ARI learns only the billing-related view. Following the TLS 1.3 handshake stages, we describe how TrustedARI distributes key material across the following four phases to realize these properties. Key Exchange Phase. The agent and ARI first jointly emulate the client side of an ECDHE exchange with the service provider. Specifically, the agent and ARI utilize ECtF [11] to generate a secretshared input key ⟨DHE⟩, which is further expanded into the handshake secret ⟨HS⟩. To reduce the overhead of 2PC computation, we incorporate a pre-computation and reuse strategy [44] that caches intermediate SHA-256 compression states, significantly optimizing the 2PC-assisted HKDF expansions for deriving ⟨dHS⟩, ⟨CHTS⟩, and ⟨SHTS⟩. To bind the connection to the intended endpoint, ARI delivers its shares of the handshake traffic secrets (i.e., CHTSR and SHTSR ) to the agent, enabling the agent to locally derive the handshake keys (tkchs , tkshs ) , avoiding expensive 2PC for handshake-key derivation. Crucially, since ARI never obtains the complete server-side handshake traffic secret SHTS, it cannot forge the server-authentication transcript or substitute an unintended service provider [29]. Service Provider Authentication Phase. ARI forwards the TLS handshake messages from the service provider to the agent, including the provider’s Certificate, SCV, SF, etc.. Using the locally reconstructed SHTS, the agent decrypts the server handshake flight, verifies the service provider’s certificate and CertificateVerify message, and expands the Server Finished key fks to validate the Finished MAC. This phase ensures that the agent can independently authenticate the intended service endpoint, without relying on ARI to perform authentication and prove the result using expensive zero-knowledge proofs, as in existing TLS oracles [11]. Application Key Generation Phase. After the service provider is authenticated, the agent and ARI jointly derive the application traffic secrets while preserving the role-specific separation. They first derive the secret-shared master secret ⟨MS⟩ from ⟨dHS⟩, and then expand it into the client-side and server-side application traffic secrets, i.e., ⟨CATS⟩ and ⟨SATS⟩. Here, the same pre-computation and caching strategy is applied to the HKDF expansions, reducing the 2PC overhead for deriving the application traffic secrets ⟨CATS⟩ and ⟨SATS⟩, application traffic keys ⟨tkcapp ⟩ and ⟨tksapp ⟩, and their corresponding initialization vectors ivcapp and ivsapp . The resulting keys are released according to their roles in the subsequent ARI-mediated interaction. The client-side application key tkcapp remains secret-shared between the agent and ARI, so that service requests can only be encrypted collaboratively. In contrast, the server-side application key tksapp is released only to the agent, so that the agent can decrypt the complete response from the service provider while ARI remains limited to its authorized billing-related view. To ensure that this release remains bound to the authenticated TLS session, the agent first commits to its share tkAsapp before ARI reveals its share tkR sapp . This ordering prevents the agent from adaptively manipulating its key share after seeing ARI’s share, thereby supporting later verification of billing-related claims while keeping ARI excluded from the full response plaintext. 6
(a) Current Plaintext ARI POST /v1/orders HTTP/1.1\r\n Host: api.shop.example\r\n Authorization: Bearer sk_9F7A2C\r\n Content-Length: 76\r\n\r\n {"buyer":"Bob","addr":"10 Downing St","coupon":"WINTER50", "item":"SKU-0941"} (b) Naïve Method POST /v1/orders HTTP/1.1\r\n Host: \r\n Authorization: Bearer \r\n Content-Length: 76\r\n\r\n {"buyer": ,"addr": "coupon": , "item":
, }
(c) Privacy-Preserving Query-Construction POST /v1/orders HTTP/1.1\r\n Host: (Rs, 𝑠! , [𝑔! ], h! )\r\n Authorization: Bearer (Rf, 𝑠" , 𝑔" , h" ) \r\n Content-Length: (Xs, 𝑠# , [𝑔# ], h# ) \r\n\r\n {"buyer": (As, [𝑠$ ], [𝑔$ ], ℎ$ ) , "addr": (As, [𝑠% ], [𝑔% ], ℎ% ) , "coupon": (Rs, 𝑠& , [𝑔& ], h& ) , "item": (Af, [𝑠' ], 𝑔' , ℎ' ) } R's Byte A's Byte
R's Segment
A's Segment
Shared Segment
Figure 3: An example of a query template and its cryptographic abstraction for Agentic Tool Routing. Client Finished Phase. To finalize the handshake, the agent locally expands the client finished key fkc using the reconstructed CHTS. If the service provider requires client authentication, the agent first encrypts and sends the required client-authentication messages, such as its Certificate and CertificateVerify, through ARI as a blind relay. The agent then generates the Client Finished (CF) message, which ARI forwards to the service provider to complete the TLS handshake. Summary. At the end of the handshake, the application traffic keys establish the following security state: the client-side key tkcapp remains secret-shared between the agent and ARI to enable collaborative request encryption, while the server-side key tksapp is reconstructed only by the agent to ensure response confidentiality and integrity. We provide the detailed ARI-adapted three-party handshake protocol Πths in Appendix B. Crucially, the handshake is a one-time per-endpoint cost incurred before runtime service invocations, allowing the TLS channel to be retained and reused across subsequent requests. When the agent needs to interact with multiple service providers, these per-endpoint setups are executed in parallel.
5
Privacy-Preserving Query-Construction
In current ARI-mediated invocations, the agent sends its request context to ARI in plaintext and relies on ARI to complete the service invocation by adapting the request to the provider-specific format and adding any necessary ARI-held invocation data (e.g., credentials), and forwarding it to the service provider. This plaintext request-construction step exposes sensitive agent-side information (e.g., private prompts in LLM routing, or sensitive tooling parameters) and leaves the agent without cryptographic assurance that these fields are processed unchanged by ARI when constructing the provider-facing request. Therefore, TrustedARI introduces a privacy-preserving query-construction protocol that enables the agent and ARI to collaboratively construct the final encrypted request without revealing any private inputs to each other. For clarity, we use Agent Tool Routing as a running example, where an agent relies on ARI to invoke a managed e-commerce checkout service on its behalf, as illustrated in Figure 3. In this example, ARI supplies the service-specific endpoint identifier, the required API credentials, and enterprisenegotiated promotional incentives (i.e., coupon). The agent supplies private buyer identities (i.e., buyer), delivery destinations (i.e., addr), and the target product (i.e., item). 7
5.1
Naive Method
We first consider a simple content-hiding approach for constructing requests. Recall that, with an AES-GCM ciphersuite, TLS record encryption generates CTR-mode keystream blocks from the client application traffic key tkcapp . For a plaintext block pi , the keystream ki and resulting ciphertext ci are derived as: ki = AES(tkcapp , ctri ); ci = ki ⊕ pi (1) where ctri denotes the counter used for the i-th plaintext block. Since ⟨tkcapp ⟩ is secret-shared, both parties can execute a 2PC protocol to compute keystream shares ⟨ki ⟩. As shown in Figure 3(b), a naive method is to instantiate the request skeleton as an ownership-labeled byte template with fixed byte offsets. The public syntax bytes are fixed by the template. For an ARI-owned field, such as the coupon value "WINTER50", the ARI places 10 bytes of plaintext at the designated positions, while the agent contributes an equal-length all-zero byte string as a placeholder. Conversely, for an agent-owned field, such as the buyer value "Bob", the agent places the plaintext bytes and the ARI contributes equal-length zeros. Given the keystream shares generated under the secret-shared TLS key, the parties can XOR their byte contributions with the corresponding keystream shares to obtain ciphertext shares, which are then opened as a standard TLS ciphertext. However, this strawman protects only byte contents: because every private field must occupy predetermined positions with predetermined lengths, the template itself leaks structural metadata such as the exact length of a recipient address or coupon code. 5.2
Protocol Design
To address this problem, our protocol enables collaborative query-construction while hiding not only the content of private fields, but also their precise boundaries and lengths. As illustrated in Figure 3(c), TrustedARI represents each variable field as a padded segment with a public maximum length, so that the actual string is hidden inside a fixed-length buffer. Formally, the public query template is defined as a sequence of segment descriptors T = [τ1 , . . . , τL ], where each descriptor τi = (θi , hi ) specifies the segment category θi and its public padded length hi . An instantiated segment is represented as Ei = (θi , ⟨si ⟩, ⟨gi ⟩, hi ), where ⟨si ⟩ and ⟨gi ⟩ are secret shares of the padded content and its actual length, respectively. For single-owner fields, the owner locally prepares the plaintext value and its length before secret-sharing them; for public syntax, the content and length are both public. We classify the segments into three categories. Public segments (P) contain static protocol syntax or JSON delimiters, where the true length g equals the padded length h. Fixed-length private segments include agent-owned Af , ARI-owned Rf , and secret-shared Xf segments whose true lengths are public constants. For example, the ARI-owned bearer token in Figure 3 can be modeled as an Rf segment when the credential format has a fixed length, while the agent-owned item field can be modeled as a Af segment when it follows a fixed-format identifier. Structure-hidding private segments include As , Rs , and Xs segments whose true lengths are secret-shared. For example, the buyer identity and address are As segments, and the ARI-selected coupon can be represented as an Rs segment if the server does not want to reveal the coupon code or its length. Before assembly, each owner pads its content to the public length h with null bytes (i.e., “0x00”) to hide the actual length g. To assemble these three types of segments into a valid request, TrustedARI must ensure that private segments are concatenated correctly even when their precise lengths are hidden. As illustrated in Figure 4, we define two distinct concatenation paths based on whether the preceding segment’s length is public. Local Deterministic Concatenation (LDC). We first consider the case where the preceding segment El has a public length, as illustrated in Figure 4(a). In this scenario, since the boundary of content sl = “AB” is known, the starting position for joining the content sr = “XYZ0” of segment Er is also deterministic. Here, “0” denotes a null byte. Thus, to obtain the secret shares of the merged segment Em , one party simply appends a hr -byte placeholder (i.e., “0x00”) to sl , while the other party prepends a hl -byte placeholder to sr . Consequently, both parties can compute the shares locally without any 2PC protocols. The resulting segment Em is secret-shared by both parties: one holds ⟨Em ⟩0 = {θm , sl ∥0x00hr , gl , hl + hr } and the other one holds ⟨Em ⟩1 = {θm , 0x00hl ∥sr , gr , hl + hr }. Thus, Em = {θm : Xs , sm : (sl ∥0x00hr ) ⊕ (0x00hl ∥sr ) = “ABXYZ0”, gm : gl + gr = 5, hm : hl + hr = 6}. 8
Fixed-length Segment E"
𝑔!
Private-length Segment E#
Private-length Segment E"
Padding
Padding
𝑔"
s# = XYZ \0
s! = AB h! Private-length Segment
𝑔!
s! = AB \0\0
h"
E$ %
s$ % = s! Placeholder
AB \0\0\0\0
Private-length Segment E$
𝑔&
Padding
s$ = XYZ \0 h&
h!
Private-length Segment
E$ &
E# ← ℱ%&' ( E! , E$ )
Placeholder
s#
Private-length Segment E#
s$ & =
g " = 𝑔# + 𝑔$
\0\0 XYZ \0
Padding
s# = AB XYZ \0\0\0
h! ℎ& = ℎ! + ℎ' g # ( = 𝑔'
h" ℎ& = ℎ! + ℎ' g # $ = 𝑔%
ℎ% = ℎ! + ℎ$
(a) LDC
(b) SHC
Figure 4: An example of the local deterministic concatenation (LDC) and the structure-hiding concatenation (SHC). Protocol (⟨sm ⟩, ⟨gm ⟩, hm ) ← ΠSHC (⟨sl ⟩, ⟨gl ⟩, hl , ⟨sr ⟩, ⟨gr ⟩, hr ) Input. Two-party bitwise secret-shares of the left string ⟨sl ⟩, the right string ⟨sr ⟩, and arithmetic shares of the length of sl ’s content ⟨gl ⟩, the length of sr ’s content ⟨gr ⟩, respectively. The length of the padded string is hl (hr ), which is public for both parties. Output. A secret-shared string ⟨sm ⟩ and its actual length ⟨gm ⟩ and public padded length hm . 1 k ← ⌈log2 (hl + hr )⌉ # Bitwidth. 2
⟨ul ⟩ ← ⟨sl ⟩ ∥ 0 hl −gl ; ⟨ur ⟩ ← ⟨sr ⟩ ∥ 0 hr −gr .
⟨va ⟩ ← ⟨ul ⟩ ∥ 0 hr ;⟨v0 ⟩ ← 0 hl ∥ ⟨ur ⟩. 4 ⟨d⟩arith ← hl − ⟨gl ⟩; # Locally compute shares. 5 ⟨d⟩xor ← FA2B (⟨d⟩arith , k); # Convert d to XOR-share. 6 ⟨vb ⟩ ← ΠBlindRotate (⟨v0 ⟩, ⟨d⟩xor , k); # OT-based left shift. 7 ⟨sm ⟩ ← ⟨va ⟩ ⊕ ⟨vb ⟩; ⟨gm ⟩ ← ⟨gl ⟩ + ⟨gr ⟩; hm = hl + hr .
3
Protocol 1: The structure-hiding concatenation protocol. Structure-Hiding Concatenation (SHC). In contrast, when the length of the preceding segment El is shared between two parties, naively joining two segments introduces malformed null bytes within the resulting segment. For instance, in Figure 4(b), appending “XYZ0” to “AB00” yields “AB00XYZ0”, which introduces two null bytes between the actual contents “AB” and “XYZ”. Therefore, we require a two-party computation protocol, named the Structure-Hiding Concatenation (SHC) protocol ΠSHC , to extract and merge the real content, while shifting all these padded null bytes to the end of the joined segment (i.e., “ABXYZ000”). Formally, ΠSHC securely merges a left segment El = (θl , ⟨sl ⟩, ⟨gl ⟩, hl ) and a right segment Er = (θr , ⟨sr ⟩, ⟨gr ⟩, hr ) into a secret-shared result Em = (Xs , ⟨sm ⟩, ⟨gm ⟩, hm ). We summarize it in Protocol 1. As shown in Line 2–3, ΠSHC first prepares extended vectors ⟨va ⟩ and ⟨v0 ⟩ by padding the shares of sl and sr to a total length hm = hl + hr . To eliminate these null bytes between the actual contents, the parties compute a secret shift distance ⟨d⟩ = hl − ⟨gl ⟩ (mod 2k ). In Line 6, we invoke the ΠBlindRotate , which utilizes FMUX2 to perform an oblivious left-shift of ⟨v0 ⟩ by the secret distance d. This ensures that the two segments are seamlessly joined at the sensitive boundary gl via a final XOR sum ⟨va ⟩ ⊕ ⟨vb ⟩, resulting in a correctly compacted segment Em where the total length ⟨gm ⟩ = ⟨gl ⟩ + ⟨gr ⟩ remains hidden from both parties. We defer the detailed ΠBlindRotate in Appendix C. We maintain the content length g as an arithmetic share. This choice requires only a single FA2B conversion within ΠSHC , whereas bitwise sharing would require two FB2A conversions. We provide a detailed performance evaluation of different sharing domains in § 7.3.2. Collaborative Query Assembly and Encryption. Based on ΠLDC (i.e., the LDC protocol) and ΠSHC , the agent and ARI collaboratively assemble the full request by following an assembly plan Ω. As detailed in Protocol Πquery in Protocol 2, Ω defines a series of iterative assembly steps ω = (i, k, j), where the parties merge previously assembled segments E[i,k] and E[k+1,j] into a larger range E[i,j] .
9
Protocol (Q̂, σ) ← Πquery (T , {E}, Ω, ⟨tkcapp ⟩) Input. A and R agree on a public template T = [τ1 , . . . , τL ], where each segment descriptor τi = (θi , hi ) specifies the segment category and padded length. The parties prepare initial segments {E} = [E[1,1] , . . . , E[L,L] ], where each E[i,i] = (θi , ⟨si ⟩, ⟨gi ⟩, hi ) contains the padded content and its actual length. They hold an assembly plan Ω = [ω1 , ω2 , . . . ] where each step ω = (i, k, j) defines a concatenation: E[i,j] = E[i,k] ⊞ E[k+1,j] , merging the previously assembled range [i, k] with [k + 1, j]. They shared the session key ⟨tkcapp ⟩. Output. The encrypted query Q̂ and its GMAC tag σQ . for each ω = (i, k, j) ∈ Ω do: # Iterative assembly. 2 El = E[i,k] = (θl , ⟨sl ⟩, ⟨gl ⟩, hl ). 3 Er = E[k+1,j] = (θr , ⟨sr ⟩, ⟨gr ⟩, hr ). 4 if θl ∈ {P, Af , Rf , Xf } then # ⊞ instantiates ΠLDC . 1
⟨sm ⟩ ← (⟨sl ⟩∥0x00hr ) ⊕ (0x00hl ∥⟨sr ⟩). 6 ⟨gm ⟩ ← gl + ⟨gr ⟩ ; hm ← hl + hr . 7 else # ⊞ instantiates ΠSHC . 8 (⟨sm ⟩, ⟨gm ⟩, hm ) ← ΠSHC (⟨sl ⟩, ⟨gl ⟩, hl , ⟨sr ⟩, ⟨gr ⟩, hr ) 9 Em = E[i,j] ← (θm , ⟨sm ⟩, ⟨gm ⟩, hm ). 10 ⟨Q⟩ ← E[1,L] .⟨s⟩. # Final content share. 5
11
(Q̂, σQ ) ← Π2PC-AEAD (⟨Q⟩, ⟨tkcapp ⟩). # AEAD.
Protocol 2: The privacy-preserving query-construction. For each step, the protocol adaptively selects the concatenation primitive: if the preceding segment has a public true length according to the template metadata, it triggers the efficient ΠLDC update; otherwise, it invokes ΠSHC protocol to handle hidden boundaries. Once the iterative assembly is complete, the parties obtain the final secret-shared query string ⟨Q⟩ by extracting the content part of the final segment E[1,L] . Once the final secret-shared query string ⟨Q⟩ is obtained, the agent and ARI jointly execute a 2PCAEAD circuit Π2PC-AEAD using their respective shares of the query and the client application key ⟨tkcapp ⟩. Internally, the parties securely derive keystream shares ⟨k⟩ = AES(⟨tkcapp ⟩, IV) through a 2PC evaluation, then they compute ciphertext Q̂ = ⟨k⟩ ⊕ ⟨Q⟩ and its GMAC tag σQ . The ciphertext and tag are then opened to both parties; ARI then forwards them to the service provider as a standard TLS-compliant record. Due to the page limit, we defer the security proof to Appendix E. 5.3
Extensions
Concatenation Planning. Repeated use of ΠSHC introduces a “structural contamination” problem. Specifically, once a newly assembled range has a secret-shared true length, its end boundary becomes hidden from both parties. For example, after ⟨E[1,2] ⟩ ← ΠSHC (⟨E[1,1] ⟩, ⟨E[2,2] ⟩), any later range (e.g., E[3,3] ) must be appended to E[1,2] using ΠSHC , even if it contains only public or fixed-length segments, because its placement depends on the hidden end boundary of E[1,2] . To minimize the cumulative overhead, we observe that the complexity of a single ΠSHC operation is O((hl + hr ) log (hl + hr )). Therefore, we formulate the request assembly as an optimization problem to find a concatenation order that minimizes the total cost. We define Γ(i, j) as the minimum cost to assemble a contiguous sequence of segments from index i to j. The objective is to minimize the total cost Γ(1, L) for L initial segments, formulated as Γ(i, j) = mini≤k<j {Γ(i, k) + Γ(k + 1, j) + ∆(i, k, j)}, where ∆(i, k, j) represents the marginal cost of merging segment ranges E[i,k] and E[k+1,j] . We set ∆(i, k, j) = 0 when the left range E[i,k] has a public true length according to the template metadata, so the merge can be performed locally using the efficient ΠLDC primitive. Otherwise, ∆(i, k, j) is set to the estimated communication and computation cost of the corresponding ΠSHC operation. By solving this optimization via dynamic programming, TrustedARI generates an optimal plan Ω that minimizes the estimated total cost of expensive ΠSHC . Handling Protocol-Specific Metadata. Some protocols require metadata that depends on private field lengths. For example, an HTTP Content-Length header must encode the exact body length 10
Public Input
Witness
Target Field
Delimiter
Parse
R = {"A": "Alice","B": 100, "C": [ "Fresno", {"D": true,"E": null}] , "K":"V" , "F": {"G": 3.1415}} ''Parsing'' Circuit: 𝑶(𝓛!"#$% )
d=1
-1
+2
d=0
Figure 5: Overview of the localized parsing circuit for verifiable billing. as an ASCII decimal string, while this length may depend on secret-shared payload segments. To handle such cases, TrustedARI treats the metadata field as a secret-shared segment and computes its value with P a small MPC metadata-generation primitive. For Content-Length, the parties compute ⟨gbody ⟩ = i∈Ibody ⟨gi ⟩, where Ibody denotes the body segments, and convert this arithmetic-shared integer into an XOR-shared ASCII decimal string using an Integer-to-String primitive ΠI2S . The resulting string is then assembled into the request like other secret-shared segments, without revealing the computed body length during construction. We defer the details of ΠI2S to Appendix D. Beyond HTTP. Although we instantiate TrustedARI with HTTP requests, the segment-based abstraction is not HTTP-specific. It applies to any application-layer message that can be decomposed into public syntax and private fields. For such protocols, developers can define protocol-specific segment descriptors and metadata-generation primitives, while reusing the same LDC/SHC-based assembly framework.
6
Verifiable Billing Protocol
ARI-mediated invocations often use usage-based billing (e.g., per-invocation or per-token billing), where metering fields (e.g., success in tool response or token_usage in LLM response) are embedded in the service responses. However, because TrustedARI restricts response decryption exclusively to the agent via tksapp , the ARI remains blind to these fields and must rely entirely on self-reported metering by the agent. This information asymmetry allows an economically motivated agent to under-report usage (e.g., by claiming that a billable invocation failed or deflating token consumption). To be compatible with the existing settlement conventions, TrustedARI implements a verifiable billing protocol based on ZKP, requiring the agent to generate a proof demonstrating that its reported billing metrics are faithfully extracted from the encrypted TLS response record under the committed server-application traffic key tksapp . In our proving circuit, the target billing attributes consist of a predefined selector φ and the agentreported value v, both of which are treated as public inputs by the verifier (i.e., ARI). Consequently, TrustedARI only needs to assert two orthogonal properties in the ZKP circuit: (i) structural isolation: the proof must show that the reported value is the value associated with the predefined selector φ at the expected JSON path/depth, rather than a matching substring inside an unrelated nested field or string literal. For example, in Figure 5, the selector “K” is a top-level member of the response payload rather than being nested within another field like “G”. (ii) cryptographic binding: every byte used to satisfy this selector/value check must be the decryption of the public TLS response ciphertext under the committed server-application traffic key tksapp , e.g., the selector “K” is located at byte offset 58. Existing TLS-oracle systems typically handle such checks by reconstructing selected plaintext chunks inside the circuit [50] or by deriving a full parsing structure over the response [6]. These generalpurpose designs are well-suited for flexible web attestation, yet their cryptographic binding cost scales with the amount of ciphertext that must be decrypted and parsed in-circuit. In our billing setting, the target field is predefined by the provider schema, allowing TrustedARI to localize both decryption and parsing to a boundary-anchored window around φ : v. TrustedARI designs a localized parsing circuit that enforces both properties only over a selected response window. As illustrated in Figure 5, the circuit maintains arithmetized parser states for string boundaries, escape characters, and JSON depth. The depth accumulator d is updated only outside string literals, ensuring that braces appearing inside strings do not affect the structural check. The circuit then verifies that the target key-value pair φ : v appears at the expected syntactic depth. To reduce both parsing and cryptographic decryption constraints, TrustedARI uses an adaptive boundary window selection. The window descriptor ω = (o, ℓ, ρ) specifies the local ciphertext window by its block offset o, length ℓ, and parsing direction ρ ∈ {fwd, rev}. The protocol considers 11
Circuit Ckt(X, W) : • X = (tkRsapp , comA , R̂, r, φ, v, ω, dt , j, k) • W = (tkAsapp , Rlocal ) • comA = H(tkAsapp , r), tksapp = tkAsapp ⊕ tkRsapp • Dectksapp (R̂, ω) = Rlocal , |Rlocal | = Llocal • Set b0 ← 0, e0 ← 0, d0 ← 0 # string, escape, depth • ∀i ∈ [1, Llocal ] where ci ← Rlocal [i]: κ123 ← 1{ci =123} , κ125 ← 1{ci =125} # Track ‘{’ and ‘}’ κ34 ← 1{ci =34} , κ92 ← 1{ci =92} # Track ‘"’ and ‘\’ ei = (1 − ei−1 ) · bi−1 · κ92 # Track escape state bi = ei−1 · bi−1 + (1 − ei−1 ) · [bi−1 · (1 − κ34 ) + (1 − bi−1 ) · κ34 ] # Track string boundary di = di−1 + (1 − bi−1 ) · (κ123 − κ125 ) # Track depth • Enforce Rlocal [j . . . k] encodes field φ : v at depth dt .
Figure 6: Arithmetic constraint specification for the verifiable billing circuit Ckt for a forward-parsing window. two boundary-anchored windows that contain the target key-value pair φ:v: a prefix window parsed forward from the JSON start boundary, and a suffix window parsed backward from the JSON terminal boundary using the corresponding reverse depth transition. Because AES-GCM encryption is countermode based, the circuit only needs to prove decryption for the ciphertext blocks covered by ω, rather than for the full response. TrustedARI then selects the shorter candidate window. For example, if reaching the billing field requires decrypting and parsing five AES blocks from the start boundary but only three AES blocks from the terminal boundary, TrustedARI selects the suffix window and reduces the effective proof length to Llocal . Notably, by positioning the target data near the response boundaries—a configuration negotiable with the service provider—TrustedARI maintains negligible proving overhead independent of the total response length. Formal Statement. We formalize billing attestation as an NP relation checked by the parsing circuit Ckt(X, W) in Figure 6. The public statement is X = (tkR sapp , comA , R̂, r, φ, v, ω, dt , j, k), where R̂ is the ARI-provided TLS response record, ω identifies the local ciphertext window and parsing direction, dt is the target JSON depth, and [j, k] bounds the target key-value pair within the local plaintext. The private witness is W = (tkAsapp , Rlocal ), consisting of the agent’s key share and the decrypted local plaintext segment. Inside the circuit, Ckt checks the commitment comA = H(tkAsapp , r), reconstructs tksapp , and constrains the selected ciphertext blocks R̂[ω] to decrypt to Rlocal . It then tracks string, escape, and depth states in the selected parsing direction and enforces that Rlocal [j . . . k] encodes the public key-value pair φ : v at depth dt . Completed Protocol. The verifiable billing protocol follows a standard NIZK lifecycle. The initial setup phase produces the proving key pk and verification key vk based on the definition of the circuit Ckt. To initiate billing verification, the agent executes the prove algorithm, taking the public inputs X, its private witness W, and pk to generate a succinct proof π. This proof is then submitted to the ARI. The ARI concludes the process by running the verify algorithm using vk, π, and X. If the algorithm outputs true, ARI is cryptographically assured that the billing metrics are authentic and structurally valid within the original TLS record, even without direct access to the plaintext response. Crucially, the agent can asynchronously generate proofs in parallel after collecting multiple responses for batched settlement, avoiding blocking the active service invocations. TrustedARI can integrate the billing proof to an X402-style escrow settlement [19, 18]. The payment lifecycle follows two phases. (i) a deposit and lock phase where funds are escrowed via the x402 engine, and (ii) a settle and distribute phase where the proof π triggers the automated fee distribution based on authentic usage. Details are deferred to Appendix F.
7
Evaluation
Our evaluation is organized into two complementary dimensions: a formal security analysis of our protocols and a comprehensive experimental study. Security Analysis. We integrate the handshake (§ 4), query (§ 5), and billing (§ 6) protocols into a unified protocol Πsys . Due to the page limit, we provide a proof sketch that Πsys securely realizes the 12
DiStefano [11] Agent-ARI
TLS Online
TrustedARI Agent-ARI
TLS Online
Network I (s) 12.27 ± 0.34 1.14 ± 0.09 5.73 ± 0.10 1.00 ± 0.10 Network II (s) 14.14 ± 0.42 1.32 ± 0.11 6.46 ± 0.10 1.20 ± 0.04 Network III (s) 24.64 ± 0.14 3.51 ± 0.08 13.52 ± 0.28 3.38 ± 0.10 Network IV (s) 41.79 ± 0.41 8.13 ± 0.07 28.18 ± 0.47 7.40 ± 0.07 Comm. (MB) 220.48 0.39 133.62 0.36 Table 1: Phase-wise running time and communication overhead of the three-party handshake protocol. ideal functionality Fsys against a semi-honest adversary. We defer the complete protocol specification and the security proof to Appendix G. Experimental Evaluation. To evaluate the performance and deployability of TrustedARI, we conduct extensive experiments on both real-world and synthetic service APIs. Our evaluations center around the following questions: the efficiency of our three core components—the ARI-adapted handshake (RQ1), the privacy-preserving query-construction protocol (RQ2), and the verifiable billing protocol (RQ3), as well as whether TrustedARI is readily deployable without modifying service providers (RQ4). 7.1
Implementation & Setup
Implementation. We implement a prototype of TrustedARI based on DiStefano [11] and FreeAuth [17]. We extend the codebase by approximately 9,000 lines of C++ and 3,000 lines of Go code. Our system is built on a TLS 1.3 protocol stack. The handshake (§4) and query-construction (§5) protocols are implemented in C++ using EMP-toolkit [41], and integrated with BoringSSL [21]. We reproduce its pre-computation and reuse optimization [44] since the official implementation is closed-source. Our query-construction protocol (§5) incorporates IKNP OT extension [27], which avoids heavy preprocessing and decreases communication overhead. The verifiable billing protocol (§6) is implemented using the Gnark library [10] with the Plonk [20] proving scheme over the BN254 scalar field, utilizing the ZK-friendly MiMC [5] hash function. We construct a composite baseline from TLS oracle systems: DECO [50] for proving TLS payloads and ZKMB [22] for proving packet headers. Specifically, we re-implement the closed-source DECO and port the jsnark-based ZKMB implementation to the same Gnark/Plonk framework for a fair comparison. Real-world Service Dataset. We select 10 diverse and representative service APIs used in ARImediated workflows, including GitHub, Google, and OpenAI, and covering categories such as source code management, database retrieval, and LLM inference. The dataset has an average query length of 542.8 bytes, ranging from 3 to 49 segments (averaging 20 segments per query); and an average response length of 723.4 bytes. This dataset is used to evaluate the end-to-end efficiency of our query construction and billing protocol in TrustedARI. A detailed breakdown of the API categories is provided in Appendix H. Setup. Our evaluation environment is a Linux server equipped with a multi-core x86_64 Intel CPU at 2.60GHz. To evaluate performance under diverse conditions, we utilize tc and network namespaces to simulate several environments: Network I (5000 Mbps, ≤ 1 ms), Network II (1000 Mbps, 1 ms), Network III (200 Mbps, 10 ms), and Network IV (200 Mbps, 50 ms). Results are averaged over five runs to minimize measurement noise. 7.2
RQ1: Efficient Three-Party Handshake
To demonstrate the efficiency gains achieved through our ARI-specific handshake design, we evaluate the performance of our ARI-adapted key scheduling against the state-of-the-art general third-party TLS handshake protocol DiStefano [11]. Table 1 summarizes the running time and communication across various network environments. We benchmark the protocol across two phases: (i) the AgentARI phase, which captures the precomputation between the Agent and ARI and can be executed asynchronously before the TLS Server is involved, and (ii) the TLS Online phase, which represents the synchronous cryptographic operations requiring real-time interaction with the service provider. 13
Computation Time (s)
ID
Communication (MB)
Structure
Content
Total
Structure
Content
Total
0.07 0.18 0.46 0.07 0.18 0.15 0.18 0.21 0.30 0.14
0.96 0.91 0.97 0.46 1.52 0.81 1.44 1.53 1.42 1.34
1.03 1.09 1.43 0.53 1.70 0.96 1.62 1.74 1.72 1.48
0.19 0.47 1.39 0.16 0.54 0.63 0.66 0.56 0.87 0.38
36.92 33.04 37.08 18.86 54.10 29.79 55.14 57.54 49.30 48.86
37.11 33.52 38.47 19.03 54.64 30.42 55.80 58.10 50.17 49.24
1 2 3 4 5 6 7 8 9 10
6.0
Bitwise Sharing Arithmetic Sharing
4.5 3.0 1.5 0.0 23
24
25
26
27
28
Communication (MB)
Running Time (s)
AVG 0.19 1.13 1.32 0.58 42.06 42.65 Table 2: Per-party computation time and communication cost breakdown of Πquery on real-world downstream APIs.
Input Size (B)
4.5
Bitwise Sharing Arithmetic Sharing
3.0 1.5 0.0 23
24
25
26
27
28
Input Size (B)
Figure 7: Running time and communication of ΠSHC under arithmetic and bitwise sharing (in Network II). As shown in Table 1, our ARI-specific handshake protocol achieves a substantial latency reduction ranging from 32.57% to 53.32% in the Agent-ARI phase, translating to an end-to-end speedup of 28.72% to 50.47% across various network settings. Regarding the TLS Online phase, the online overhead ranges from 1.00 to 7.40 seconds, which remains below a 10-second practical timeout budget for online TLS connection establishment. Furthermore, TrustedARI reduces the total communication cost by 39.34%, from 220.87 MB to 133.98 MB. We clarify that the handshake is a one-time per-endpoint cost incurred before runtime service invocation, and setups for different providers run in parallel. Once the connection is established, subsequent queries can reuse the established TLS channel. 7.3 7.3.1
RQ2: Efficient Query Construction Performance on Real-world Services
We evaluate the performance of our privacy-preserving query-construction protocol on our real-world service dataset. Table 2 summarizes the breakdown of local computation time and communication cost into structure-hiding and content-hiding processing, excluding network latency. Specifically, the structure-hiding processing refers to the iterative assembly of all segments {E}, after which parties extract the final secret-shared query string ⟨Q⟩ from the content part of the last segment E[1, L]. In contrast, the content-hiding processing involves the subsequent encryption of ⟨Q⟩ into ciphertext Q̂ and a GMAC σQ using a 2PC-AEAD protocol, which is the same 2PC-AEAD step required by general TLS-oracle systems and the content-only baseline. The results indicate that, compared to a naive approach that only protects query content, our design introduces modest additional cost to provide comprehensive protection for both content and structure. Specifically, the structure-hiding part accounts for an average of only 0.19 seconds of computation time (14.29% of total time) and 0.58 MB of communication (1.36% of total communication). These results show that hiding query structure incurs only a small marginal overhead beyond content-hiding encryption. 14
7 6 Bitwise Arithmetic
5 4
24
26
28
210
212
Communication (KB)
Running Time (ms)
8
64 56 48 Bitwise Arithmetic
40 32 24
26
Input Size (B)
28
210
212
Input Size (B)
Sequential Optimal
2.0 1.5 1.0 0.5 8
12
16
20
Communication (MB)
Running Time (s)
Figure 8: Running time and communication of ΠI2S under arithmetic and bitwise sharing (in Network I). 2.5
Sequential Optimal
2.0 1.5 1.0 0.5
# of Segments
8
12
16
20
# of Segments
Figure 9: Running time and communication cost of sequential and optimized concatenation plans (in Network II). 7.3.2
Impact of Arithmetic Sharing
To validate our design choice of representing the content length as arithmetic shares (as discussed in § 5.3), we compare the performance of ΠSHC with a baseline that employs bitwise sharing. Our arithmetic sharing variant incorporates byte-level processing and IKNP [27] OT extension to decrease communication. Figure 7 shows the running time and communication with varying input sizes (from 8 to 256 bytes) in Network II. We set α = 0.1, meaning that the padding occupies 10% of the total input length. Compared to the bitwise sharing scheme, when the input size is 8 bytes, arithmetic sharing reduces the running time from 0.360 seconds to 0.093 seconds, a 3.87× improvement. When the input size increases to 256 bytes, arithmetic sharing reduces the running time by 39.96× from 5.995 seconds to 0.150 seconds. As for the communication, arithmetic sharing reduces the baseline’s overhead by 1.09× when the input size is 8 bytes, and by 26.85× when the input size reaches 256 bytes. Both reductions grow with the input size. Figure 8 shows the running time and communication of different sharing schemes for ΠI2S when sweeping the input string length (from 16 to 4096 bytes) with a fixed bit width k = 20. This experiment is performed in Network I to eliminate the disproportionate impact of network latency on millisecond-level operations. We observed a staircase-like growth in both metrics, as the output length gout only increments when gbody crosses decimal digit-length thresholds. Evaluation results indicate that arithmetic sharing maintains comparable performance to the bitwise baseline in ΠI2S , with a marginal overhead of only 2% on average. Despite this marginal disadvantage in ΠI2S , arithmetic sharing remains the superior choice for the overall protocol. The millisecond-level cost in ΠI2S occurs at most once per invocation and is negligible compared to the substantial gains in multiple ΠSHC rounds, where arithmetic sharing yields about 40× speedup and saves megabytes of communication. 7.3.3
Effectiveness of Optimized Concatenation Plan
We now evaluate the effectiveness of our optimal segment concatenation planning introduced in § 5.3. We compare our approach against a sequential concatenation plan, where all segments are concatenated strictly following their original sequence. Figure 9 illustrates the running time and communication for different concatenation plans as the number of segments increases (from 8 to 20) 15
ID
1 2 3 4 5 6 7 8 9 10
# of Constraints (106 )
Proving Time (s)
Verifying Time (ms)
DECO +ZKMB
Ours
DECO +ZKMB
Ours
DECO +ZKMB
Ours
22.28 6.53 8.56 57.59 9.33 1.28 38.13 24.90 9.88 27.76
1.57 0.89 0.60 0.80 0.38 0.13 0.47 0.39 0.67 0.30
108.00 28.84 50.43 215.49 53.27 8.61 236.01 125.00 52.30 109.04
8.28 4.17 3.84 4.13 2.15 0.61 2.24 3.11 4.40 2.04
9.08 4.19 2.73 5.49 6.28 2.08 3.64 5.01 5.03 5.43
5.46 3.10 5.57 2.81 3.09 2.11 2.59 3.20 3.81 2.64
AVG 20.62 0.62 98.70 3.50 4.89 3.44 Table 3: Constraint count, proving time, and verification time on real-world downstream APIs. in Network II. To simulate real-world packet structures, we construct requests starting with one group of public and structure-hiding segments (P, As , P, Rs ), followed by several groups of fixed-length segments (P, Af , P, Rf ). The core efficiency gain of our optimized plan stems from strategically ordering the assembly of segments to maximize the number of invocations of ΠLDC while minimizing the number of ΠSHC invocations. As shown in Figure 9, our optimized plan scales better as the number of segments increases. Compared to the sequential plan, when there are 8 segments, our concatenation plan reduces the running time and communication by 2.48×, from 0.67 s to 0.27 s and improves communication by 2.48×. When the number of segments increases to 20, the speedup for running time reaches 5.23× (from 2.30 s to 0.44 s), while the communication overhead is reduced by 5.86× (from 2.52 MB to 0.43 MB). These results validate that our segment concatenation plan effectively eliminates redundant 2PC concatenations, maintaining low overhead for complex, multi-segment service queries. 7.4 7.4.1
RQ3: Efficient Verifiable Billing Protocol End-to-End Performance on Real-world APIs
We evaluate the performance of our verifiable billing protocol using the real-world API dataset. Table 3 presents a comparative analysis between TrustedARI and a hybrid baseline combining ZKMB [22] and DECO [50]. Our protocol substantially reduces the constraint count and proving time, by avoiding proving the entire packet required by the baseline, while keeping verification time within a few milliseconds. On average, TrustedARI reduces the number of constraints by 33.26×, from 20.62 × 106 to 0.62 × 106 . This reduction directly improves proof generation, where the average proving time is reduced from 98.70 seconds to 3.50 seconds, representing a 28.20× speedup. Meanwhile, the average verifying time remains efficient at 3.44 milliseconds. In practice, the agent can collect multiple responses and generate their billing proofs asynchronously for batched settlement, so proof generation does not block the active service-invocation path. 7.4.2
Efficient Proving of JSON Payload
To evaluate the proving circuit efficiency across diverse scenarios, we construct a benchmark based on APIBank [30], where the service responses are formatted as JSON strings. We embed four checkpoints (CP1–CP4) at fixed structural positions within each payload to represent different target locations. We benchmark TrustedARI against two TLS-oracle baselines: DECO [50] and Coral [6]. Figure 10 (left) illustrates the proving time relative to the total JSON length, where each data point represents the average performance across all four checkpoints for a specific payload. As the payload scales, the baselines increase roughly linearly with the payload length because they exhaustively process the full JSON structure. In contrast, TrustedARI presents a significantly flatter slope, requiring an average of only 1.47 seconds of proving time (ranging from 0.94s to 2.64s). This shows that the proving cost of 16
20
DECO Coral TrustedARI
Proving Time (s)
Proving Time (s)
30
10 0 200
20
DECO Coral TrustedARI
15 10 5 0
400
600
800
CP1
JSON Length (B)
CP2
CP3
Checkpoint
CP4
Figure 10: Proving time of TrustedARI and baselines under varying JSON payload lengths and target-field locations. TrustedARI grows much more slowly with payload length by only proving the boundary window containing the targeted fields. Figure 10 (right) plots the average proving time at each specific checkpoint across the dataset to evaluate location sensitivity. For DECO and Coral, the execution curves remain flat across all checkpoints due to their full-parse design. In contrast, TrustedARI exhibits a clear positiondependent curve owing to our adaptive boundary window selection. Consequently, TrustedARI yields a substantial speedup ranging from 3.70× to 20.95× over Coral, and 7.01× to 39.69× over DECO, with the performance gain peaking when the target field is close to the beginning or end of the payload. This confirms that the cryptographic cost scales with the distance to the nearest string boundary rather than the total payload length. 7.5
RQ4: Accurate Service-Request Generation
For LLM API Routing, generating TrustedARI-compatible input is straightforward because the user prompt itself serves as the agent-owned content to be placed in the public query template. We therefore focus on the more challenging Agent Tool Routing setting, where agents must synthesize tool-specific parameters that satisfy the TrustedARI-compatible query template. To evaluate whether this template affects agent compatibility, we construct another benchmark based on APIBank [30]. Our evaluation uses 214 tool-invocation dialogues, each containing 9.98 turns on average, covering 53 APIs and 132 input parameters adapted to the TrustedARI-compatible query template. Specifically, we partition the parameters based on data ownership: 22 parameters are designated as ARI-owned, where the agent is expected to output null values, while the remaining 110 parameters are agent-owned, requiring the agent to generate semantic values. We also implement an adapter in form of a skill [7] that maps agent-generated TrustedARI-compatible requests into the protocol-level input representation. Specifically, this adapter maps each parameter into a 4-tuple segment Ei = {θi , si , gi , hi } (described in § 5.2), which then serves as the input for the privacy-preserving query-construction protocol (§ 5), collaboratively executed by the agent and ARI to produce the final encrypted query. We evaluate the compatibility of TrustedARI with existing agents by comparing the performance of generating TrustedARI-compatible requests against standard requests [30]. We use three metrics: (i) Format, which assesses whether the generated tool calls strictly adhere to the API definition, including correct parameter names, types, and the mandatory “null” assignment for ARI-owned parameters; (ii) Content, which measures the correctness of generated values relative to the conversation context; and (iii) Adapter, for TrustedARI-compatible requests, which validates the successful transformation of agent outputs into valid 4-tuple segments. Any invocation of an incorrect API or failure to follow the defined schema is counted as a failure for all metrics. We evaluate the compatibility using agents powered by three moderately-capable LLMs: Gemini-3-Flash (Gemini), GPT-5.2 (GPT), and Claude-Sonnet-4.5 (Claude). As shown in Table 4, the TrustedARI-compatible format preserves request-generation accuracy, with the largest observed drop in total accuracy being only 0.45 percentage points. This trend is also 17
Agent
Template Format(%) Content(%) Adapter(%) Total(%) APIBank 95.54 88.62 88.62 Gemini [30] ±0.76 ±0.95 ±1.01 -based TrustedARI96.34 91.53 97.29 90.43 Agent compatible ±1.38 ±0.86 ±0.54 ±1.48 APIBank 97.39 91.18 91.18 GPT [30] ±0.22 ±0.37 ±0.37 -based TrustedARI97.84 92.73 97.59 92.73 Agent compatible ±0.49 ±0.47 ±0.49 ±0.47 APIBank 97.34 91.33 91.33 Claude [30] ±0.14 ±0.22 ±0.22 -based TrustedARI95.79 92.33 96.99 90.88 Agent compatible ±1.35 ±0.68 ±0.59 ±1.46 Table 4: Service-request accuracy under the standard APIBank format and the TrustedARIcompatible template. reflected in the consistently high format and content accuracy across all agents, indicating that agents can reliably generate TrustedARI-compatible tool calls. The slightly higher content accuracy under TrustedARI stems from the designation of 22 parameters as ARI-owned, such that agents are only required to output “null” for these segments, reducing error probabilities. The adapter success rate is slightly below 100% because agents occasionally generate content exceeding the predetermined maximum length h, which prevents the adapter from mapping it into a valid segment. Our findings demonstrate that integration with our protocol is straightforward, given that even mid-tier LLM agents are fully capable of generating the required requests. Overall, these results confirm the compatibility of TrustedARI with existing agent tool-calling workflows.
8
Discussion
Service Adaptation. In real-world deployment, an agent needs to adopt a TrustedARI skill [7] that realizing agent-side TrustedARI protocols when accessing ARI. The skill maps agent inputs into template-specified request segments, which serve as inputs to the privacy-preserving queryconstruction protocol. After receiving a response, the skill decrypts it locally and extracts the required fields. To handle heterogeneous services, the ARI provisions service-specific request and response templates to the skill and keeps their versions synchronized across both sides. Thus, TrustedARI preserves the service-adaptation capability of existing ARIs: agents still program against a unified interface, e.g., a common LLM API that abstracts over provider-specific endpoints, parameters, and return schemas. Billing-Field Offset Leakage. The verifiable billing protocol reveals the byte offset of the attested billing field, because ARI specifies the local response window used by the proof. This leakage is limited to the settlement metadata: it does not reveal the remaining response contents or the boundaries of other variable-length fields. In particular, when the response contains multiple interleaved variablelength fields, one attested field offset does not, by itself, determine the layout of the remaining payload. Malicious Security. Extending TrustedARI to the malicious security model requires malicioussecurity guarantees for all three protocols. Our handshake protocol follows a malicious-secure three-party construction (see Appendix B), and the verifiable billing protocol relies on NIZK soundness against malicious provers. The remaining semi-honest component is the query construction protocol. We clarify that a malicious adversary gains only limited additional advantage even against a semi-honest query construction protocol: malformed or template-nonconforming segments, or incorrect assembly/encryption mainly lead to failed queries or denial of service, e.g., through TLS authentication failure or malformed service requests, rather than revealing private field values or enabling an adversary to overwrite unknown fields with chosen values. With additional overhead, it is possible to augment the query construction protocol with malicious-security guarantees with the garble-then-prove paradigm [44], which adds input validation for template conformance and segment well-formedness, and uses a malicious-secure backend for computation correctness. 18
9
Related Work
9.1
ARI Ecosystem and Security Enhancements
ARI has become an intermediary layer for agents to access external services. For Agentic Tool Routing, MCP [8] provides a standardized instantiation and has evolved into an open ecosystem [43], making MCP-based deployments a concrete setting for studying ARI-mediated security [52]. Existing ARI security work has attempted to mitigate privacy leakage and integrity risks. For privacy, the current best practice is to use OAuth [23], which reduces the need to expose long-term service credentials to ARI. However, OAuth does not protect runtime requests or responses when ARI mediates the invocation, and may introduce privilege-abuse or unauthorized-access risks when delegated permissions are overly broad or mishandled [32]. To protect runtime privacy, Zhao et al. [51] replace personally identifiable information (PII) with deterministic, type-preserving placeholders before invocation, but their protection is limited to query prompts in LLM API routing. For integrity, existing security mechanisms mainly follow two directions: reactive server-side scanning [45, 36, 34], which inspects ARI implementations before invocation; and runtime monitoring [9, 28, 26], which interposes auditors, gateways, or guard models to inspect interactions. These mechanisms remain heuristic and require visibility into the ARI implementation or deployment path, making them primarily applicable to open-source or locally deployed ARI. Overall, existing security enhancement mechanisms cannot provide cryptographic guarantees for request and response privacy, end-to-end integrity, or fair billing under an untrusted ARI. 9.2
TLS-Oracle
TLS-oracle systems extend a standard TLS connection between a client and an unmodified service provider with a proof mechanism, enabling the client to convince an external verifier of statements about selected response fields (e.g., the age field is above 18) without revealing other information. Existing TLS-oracle systems largely fall into two categories: notary mode [50, 44, 11, 39] and proxy mode [22, 49, 16]. In notary mode, the prover communicates directly with the TLS server and later convinces an external verifier about selected properties of the response. However, in ARI-mediated interactions, notary mechanisms would either force ARI to see plaintext for request construction [50, 44, 11], or fail to support the structural text concatenation required for multi-field query building [39]. Alternatively, applying them to ARI-mediated interactions would require proving large transcript portions (i.e., the entire query and response), where strict ciphertext alignment incurs prohibitive cryptographic overhead. Moreover, recent variants rely on restrictive assumptions such as distributed provers [39] or service-provider signatures [14], which do not hold in the ARI setting. By contrast, proxy-mode TLS-oracle targets network-middlebox settings, where an intermediary relays TLS traffic and checks whether encrypted packets satisfy network policies without learning the plaintext payload [22, 49, 16]. This design preserves confidentiality, but it confines the intermediary to ciphertext relay, which conflicts with ARI’s role in mediating heterogeneous service interfaces and fragmented provider subscriptions. In particular, ARI must use service-access metadata and support usage-based billing during the invocation, which proxy-mode systems do not provide. Overall, existing TLS-oracle designs do not support the role-specific interaction semantics required between the agent and ARI, whereas TrustedARI addresses this gap with several ARI-specific designs.
10
Conclusion
To address privacy leakage and the lack of integrity guarantees in ARI-mediated agentic interactions, we propose TrustedARI, a trust-native agentic routing infrastructure for agentic AI. TrustedARI introduces an ARI-adapted three-party TLS handshake that enables the agent and ARI to establish a standard TLS session with a service provider, while distributing key material according to role-specific interaction semantics and allowing the agent to validate the intended endpoint. Building on this handshake, TrustedARI provides a privacy-preserving query-construction protocol that allows the agent and ARI to collaboratively construct the TLS-authenticated request without revealing private inputs to each other. Finally, TrustedARI incorporates a verifiable billing protocol that preserves the confidentiality and integrity of the agent’s received response while supporting existing usage-based settlement. The experimental results across extensive settings confirm that TrustedARI is readily deployable without any modification to service providers. 19
References [1] Litellm: Al gateway to provide model access, fallbacks and spend tracking across 100+ llms., 2026. [2] Pipedream: The ai toolkit for integrations, 2026. [3] Zapier: Automate ai workflows, agents, and apps, 2026. [4] Damiano Abram, Ivan Damgård, Peter Scholl, and Sven Trieflinger. Oblivious TLS via Multiparty Computation. In Cryptographers’ Track at the RSA Conference, pages 51–74. Springer, 2021. [5] Martin Albrecht, Lorenzo Grassi, Christian Rechberger, Arnab Roy, and Tyge Tiessen. Mimc: Efficient encryption and cryptographic hashing with minimal multiplicative complexity. In International Conference on the Theory and Application of Cryptology and Information Security, pages 191–219. Springer, 2016. [6] Sebastian Angel, Sofía Celi, Elizabeth Margolin, Pratyush Mishra, Martin Sander, and Jess Woods. Coral: Fast succinct non-interactive zero-knowledge cfg proofs. In IEEE Symposium on Security and Privacy (S&P), 2026. [7] Anthropic. Agent Skills. https://platform.claude.com/docs/en/agents-and-tools/ agent-skills/overview, 2025. [8] Anthropic. Understanding remote mcp servers, 2025. [9] Manish Bhatt, Vineeth Sai Narajala, and Idan Habler. Etdi: Mitigating Tool Squatting and Rug Pull Attacks in Model Context Protocol (MCP) by Using Oauth-enhanced Tool Definitions and Policy-based Access Control. arXiv preprint arXiv:2506.01333, 2025. [10] Gautam Botrel, Thomas Piellard, Youssef El Housni, Ivo Kubjas, and Arya Tabaie. Consensys/gnark: v0.14.0, June 2025. [11] Sofía Celi, Alex Davidson, Hamed Haddadi, Gonçalo Pestana, and Joe Rowell. Distefano: Decentralized infrastructure for sharing trusted encrypted facts and nothing more. Cryptology ePrint Archive, 2023. [12] Hongyan Chang, Ergute Bao, Xinjian Luo, and Ting Yu. Overcoming the retrieval barrier: Indirect prompt injection in the wild for llm systems. arXiv preprint arXiv:2601.07072, 2026. [13] Cloudflare. Adoption & usage, Oct 2025. [14] Pierpaolo Della Monica, Ivan Visconti, Andrea Vitaletti, Marco Zecchini, et al. Acts: Attestations of contents in tls sessions. In Proceedings of the Network and Distributed System Security (NDSS) Symposium 2026, 2026. [15] Benjamin Dowling, Marc Fischlin, Felix Günther, and Douglas Stebila. A cryptographic analysis of the tls 1.3 handshake protocol. Journal of Cryptology, 34(4):37, 2021. [16] Jens Ernstberger, Jan Lauinger, Yinnan Wu, Arthur Gervais, and Sebastian Steinhorst. Origo: Proving provenance of sensitive data with constant communication. Proceedings on Privacy Enhancing Technologies, 2025. [17] Yijia Fang, Bingyu Li, Jiale Xiao, Bo Qin, Zhijintong Zhang, and Qianhong Wu. Freeauth: Privacy-preserving email ownership authentication with verification-email-free. In 2024 Annual Computer Security Applications Conference (ACSAC), pages 336–352. IEEE, 2024. [18] Lloyd Faulk. TrustEngine.sol: Escrow Smart Contract for Pre-funded, Usage-Based Payments. https://github.com/cartdotfun/evm-contracts/blob/main/contracts/ TrustEngine.sol, 2025. [19] Lloyd Faulk et al. x402 Escrow Scheme for Pre-funded, Usage-Based Payments. GitHub Issue #839, coinbase/x402, 2025. 20
[20] Ariel Gabizon, Zachary J Williamson, and Oana Ciobotaru. Plonk: Permutations over lagrangebases for oecumenical noninteractive arguments of knowledge. Cryptology ePrint Archive, 2019. [21] Google. BoringSSL. https://boringssl.googlesource.com/boringssl, 2026. [22] Paul Grubbs, Arasu Arun, Ye Zhang, Joseph Bonneau, and Michael Walfish. Zero-Knowledge Middleboxes. In 31st USENIX Security Symposium (USENIX Security 22), pages 4255–4272, 2022. [23] Dick Hardt. The OAuth 2.0 Authorization Framework. RFC 6749, October 2012. [24] Yuval Ishai, Joe Kilian, Kobbi Nissim, and Erez Petrank. Extending oblivious transfers efficiently. In Annual International Cryptology Conference, pages 145–161. Springer, 2003. [25] Jana Iyengar and Martin Thomson. QUIC: A UDP-Based Multiplexed and Secure Transport. RFC 9000, May 2021. [26] Huihao Jing, Haoran Li, Wenbin Hu, Qi Hu, Xu Heli, Tianshu Chu, Peizhao Hu, and Yangqiu Song. Mcip: Protecting mcp safety via model contextual integrity protocol. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pages 1177–1194, 2025. [27] Marcel Keller, Emmanuela Orsini, and Peter Scholl. Actively secure ot extension with optimal overhead. In Annual Cryptology Conference, pages 724–741. Springer, 2015. [28] Sonu Kumar, Anubhav Girdhar, Ritesh Patil, and Divyansh Tripathi. Mcp guardian: A securityfirst layer for safeguarding mcp-based ai system. arXiv preprint arXiv:2504.12757, 2025. [29] Jan Lauinger, Jens Ernstberger, Andreas Finkenzeller, and Sebastian Steinhorst. Janus: Fast privacy-preserving data provenance for tls. Proceedings on Privacy Enhancing Technologies, 2025. [30] Minghao Li, Feifan Song, Bowen Yu, Haiyang Yu, Zhoujun Li, Fei Huang, and Yongbin Li. Api-bank: A benchmark for tool-augmented llms, 2023. [31] Zhihao Li, Kun Li, Boyang Ma, Minghui Xu, Yue Zhang, and Xiuzhen Cheng. We urgently need privilege management in mcp: A measurement of api usage in mcp ecosystems. arXiv preprint arXiv:2507.06250, 2025. [32] Torsten Lodderstedt, Mark McGloin, and Phil Hunt. OAuth 2.0 Threat Model and Security Considerations. RFC 6819, January 2013. [33] Guozhao Mo, Wenliang Zhong, Jiawei Chen, Xuanang Chen, Yaojie Lu, Hongyu Lin, Ben He, Xianpei Han, and Le Sun. Livemcpbench: Can agents navigate an ocean of mcp tools? arXiv preprint arXiv:2508.01780, 2025. [34] Vineeth Sai Narajala, Ken Huang, and Idan Habler. Securing genai multi-agent systems against tool squatting: A zero trust registry-based approach. arXiv preprint arXiv:2504.19951, 2025. [35] OpenRouter. Openrouter: One api for any model. access all major models through a single, unified interface., 2023. [36] Brandon Radosevich and John Halloran. Mcp safety audit: Llms with the model context protocol allow major security exploits. arXiv preprint arXiv:2504.03767, 2025. [37] Deevashwer Rathee, Mayank Rathee, Nishant Kumar, Nishanth Chandran, Divya Gupta, Aseem Rastogi, and Rahul Sharma. Cryptflow2: Practical 2-party secure inference. In Proceedings of the 2020 ACM SIGSAC conference on computer and communications security, pages 325–342, 2020. [38] Eric Rescorla. The Transport Layer Security (TLS) Protocol Version 1.3. RFC 8446, August 2018. 21
[39] Sijun Tan, Weikeng Chen, Ryan Deng, and Raluca Ada Popa. Mpcauth: Multi-factor authentication for distributed-trust systems. In 2023 IEEE symposium on security and privacy (S&P), pages 829–847. IEEE, 2023. [40] Lei Wang, Chen Ma, Xueyang Feng, Zeyu Zhang, Hao Yang, Jingsen Zhang, Zhiyuan Chen, Jiakai Tang, Xu Chen, Yankai Lin, et al. A survey on large language model based autonomous agents. Frontiers of Computer Science, 18(6):186345, 2024. [41] Xiao Wang, Alex J. Malozemoff, and Jonathan Katz. EMP-toolkit: Efficient MultiParty computation toolkit. https://github.com/emp-toolkit, 2016. [42] Zhiqiang Wang, Yichao Gao, Yanting Wang, Suyuan Liu, Haifeng Sun, Haoran Cheng, Guanquan Shi, Haohua Du, and Xiangyang Li. Mcptox: A benchmark for tool poisoning attack on real-world mcp servers. arXiv preprint arXiv:2508.14925, 2025. [43] Mengying Wu, Pei Chen, Geng Hong, Aichao An, Jinsong Chen, Binwang Wan, Xudong Pan, Jiarun Dai, and Min Yang. Mcpzoo: A large-scale dataset of runnable model context protocol servers for ai agent. arXiv preprint arXiv:2512.15144, 2025. [44] Xiang Xie, Kang Yang, Xiao Wang, and Yu Yu. Lightweight authentication of web data via garble-then-prove. In Proceedings of the 33rd USENIX Conference on Security Symposium, pages 1957–1974, 2024. [45] Wenpeng Xing, Zhonghao Qi, Yupeng Qin, Yilin Li, Caini Chang, Jiahui Yu, Changting Lin, Zhenzhen Xie, and Meng Han. Mcp-guard: A defense framework for model context protocol integrity in large language model applications. arXiv preprint arXiv:2508.10991, 2025. [46] Andrew C Yao. Protocols for secure computations. In 23rd annual symposium on foundations of computer science (sfcs 1982), pages 160–164. IEEE, 1982. [47] Andrew Chi-Chih Yao. How to generate and exchange secrets. In 27th annual symposium on foundations of computer science (Sfcs 1986), pages 162–167. IEEE, 1986. [48] Yunhao Yao, Zhiqiang Wang, Haoran Cheng, Yihang Cheng, Haohua Du, and Xiang-Yang Li. Intentminer: Intent inversion attack via tool call analysis in the model context protocol. arXiv preprint arXiv:2512.14166, 2025. [49] Collin Zhang, Zachary DeStefano, Arasu Arun, Joseph Bonneau, Paul Grubbs, and Michael Walfish. Zombie: Middleboxes that Don’t snoop. In 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24), pages 1917–1936, 2024. [50] Fan Zhang, Deepak Maram, Harjasleen Malvai, Steven Goldfeder, and Ari Juels. Deco: Liberating web data using decentralized oracles for tls. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 1919–1938, 2020. [51] Lepeng Zhao, Zhenhua Zou, Shuo Li, and Zhuotao Liu. Anonymization-enhanced privacy protection for mobile gui agents: Available but invisible. arXiv preprint arXiv:2602.10139, 2026. [52] Weibo Zhao, Jiahao Liu, Bonan Ruan, Shaofei Li, and Zhenkai Liang. When mcp servers attack: Taxonomy, feasibility, and mitigation. arXiv preprint arXiv:2509.24272, 2025.
A
Zero-Knowledge Arguments
We give the formal definition of the zero-knowledge argument of knowledge used in this paper. Let G denote the setup algorithm that generates public parameters pp, and assume the NP relation R is known to both P and V. Definition Let R be an NP relation. A tuple of algorithms (G, P, V) is a zero-knowledge argument of knowledge for R if the following holds. • Correctness. For pp output by G(1λ ) and (x, w) ∈ R, ⟨P(pp, w), V(pp)⟩(x) = 1 22
• Knowledge Soundness. For any PPT prover P ∗ , there exists a PPT extractor X such that given the access to the entire executing process and the randomness of P ∗ , X can extract a witness w ∗ such that pp ← G(1λ ), π ∗ ← P ∗ (x, pp) and w ← X P (pp, x, π ∗ ), the following probability is negl(λ): Pr[(x; w) ∈ / R ∧ V(x, π ∗ , pp) = 1] • Zero knowledge. There exists a PPT simulator S such that for any PPT algorithm V ∗ , auxiliary input z ∈ {0, 1}∗ , (x; w) ∈ R, pp output by G(1λ ), it holds that ∗
View(⟨P(pp, w), V ∗ (z, pp)⟩(x)) ≈ S V (x, z) We say that (G, P, V) is a succinct argument system if the total communication between P and ∗ V (proof size) are poly(λ, |x|, log |w|). In the definition of zero knowledge, S V denotes that the simulator S is given the randomness of V ∗ sampled from a polynomial-size space. Protocol ARI-Adapted Three-party handshake Πths Agent A q
ARI R
rA ← $Z , ZA ← g
rA
q
rR ← $Z , ZR ← g rR R sends CKS ← ZA + ZR to S A and R accept SKS ← Yt from S
sskA ← $Ytrc sskR ← $Ytrs DHEA ← ECtF(sskA ) DHER ← ECtF(sskR ) HSA ⊕ HSR ← HKDF.Extract(ϕ, DHEA ⊕ DHER ) PCHS ← (IV1 , (IVA2 ⊕ IVR2 ) ← PreCompute(HSA ⊕ HSR ) CHTSA ⊕ CHTSR ← HKDF.ExpandOptm(PCHS , Label1 ∥H0 ) SHTSA ⊕ SHTSR ← HKDF.ExpandOptm(PCHS , Label2 ∥H0 ) dHSA ⊕ dHSR ← HKDF.ExpandOptm(PCHS , Label3 ∥H1 ) A accepts CHTSR and SHTSR for R R and A accept encrypted EE,SCV,SF etc. from S tkchs ← DeriveTK(CHTS) tkshs ← DeriveTK(SHTS) fks ← DeriveTK(SHTS, Label4 ∥ Hϵ ) abort if Auth(pkS , Label11 ∥H6 , SCV) ̸= 1 abort if SF ̸= HMAC(fks , H7 ) MSA ⊕ MSR ← HKDF.Extract(dHEA ⊕ dHER ,ϕ) PCMS ← (IV1 , (IVA2 ⊕ IVR2 )) ← PreCompute(MSA ⊕ MSR ) CATSA ⊕ CATSR ← HKDF.ExpandOptm(PCMS , Label5 ∥H2 ) SATSA ⊕ SATSR ← HKDF.ExpandOptm(PCMS , Label6 ∥H2 ) PCCATS ← (IV1 , (IVA2 ⊕ IVR2 )) ← PreCompute(CATSA ⊕ CATSR ) (tkAcapp ⊕ tkRcapp , ivcapp ) ← DeriveTKOptm(PCCATS ) PCSATS ← (IV1 , (IVA2 ⊕ IVR2 )) ← PreCompute(SATSA ⊕ SATSR ) (tkAsapp ⊕ tkRsapp , ivsapp ) ← DeriveTKOptm(PCSATS ) A commits tkAsapp to R A accepts tkRsapp from R tksapp ← tkAsapp ⊕ tkRsapp fkA ← DeriveTK(CHTS, Label4 ∥ Hϵ ) CF ← HMAC(fkA , H6 ) A sends CF to S through R R record layer, A and R encrypt data with tkA capp ⊕ tkcapp by AEAD
record layer, A decrypt data with key tksapp by AEAD
Protocol 3: The handshake key schedule and message flow in TrustedARI. Blue indicates message transmission; green shows optimizations over [11].
23
Subprotocol 1 ⟨K⟩ ← HKDF.ExpandOptm(PC, info) Input. PC = (IV1 , IVA2 ⊕ IVR2 ) and context string info. Output. Secret-shared output ⟨K⟩ = KA ⊕ KR . if PC not given: (IV1 , IVA2 ⊕ IVR2 ) ← PreCompute(⟨X⟩); # Compute once per shared input ⟨X⟩ and reuse. A R 2 ⟨K⟩ ← HKDF.Expand(IV1 , IV2 ⊕ IV2 , info). # 2PC-assisted expansion using cached (IV1 , IV2 ). 1
Subprotocol 2 (⟨tk⟩, iv) ← DeriveTKOptm(PCX ) Input. PCX = (IV1 , IVA2 ⊕ IVR2 ) precomputed from a shared secret ⟨X⟩. Output. Secret-shared traffic key ⟨tk⟩ and public IV iv. # Wrapper: two expansions over the same PCX . ⟨tk⟩ ← HKDF.ExpandOptm(PCX , Labelk ∥Hϵ ); 2 iv ← HKDF.ExpandOptm(PCX , Labeliv ∥Hϵ ). 1
Protocol 4: The subprotocols used in the ARI-adapted three-party handshake protocol.
B
The Detailed Handshake Protocol Πths
We present the detailed ARI-adapted Three-party handshake protocol Πths in Figure 3. Specifically, in Protocol 4, IV1 = fH (IV0 , ⟨X⟩ ⊕ ipad) via a 2PC computation and make it public, while IV2 = fH (IV0 , ⟨X⟩ ⊕ opad) remains secret. Security Proof Sketch. The security of Πths is established within the Multi-Stage Key Exchange (MSKE) model [4], following the formal framework and security games defined in Appendix E.1 of DiStefano [11]. Since our protocol maintains the core transcript binding and key dependency structure of the TLS 1.3 handshake, its security properties (e.g., Key Secrecy and Forward Secrecy) can be reduced to the same cryptographic primitives. We refer the readers to the full-version of DiStefano [11] for the detailed reduction and formal verification of these security properties.
C
The Detailed Blind Rotate Protocol ΠBlindRotate
The protocol 5 executes an oblivious left-shift on an XOR-shared vector without disclosing its content or the precise shift distance. Specifically, the protocol takes an XOR-shared length-n vector ⟨v0 ⟩ and an XOR-shared bit decomposition of a secret shift amount ⟨d⟩xor as inputs. To prevent wrap-around artifacts and handle potential overflow via zero-padding, the vector length is implicitly extended in a shift network bounded by L ← max(k, ⌈log2 (2n)⌉). The computation then proceeds bit-by-bit through an iterative layer-by-layer multiplexing cascade. At each stage ℓ, for every element index i, the protocol obliviously fetches the unshifted share ⟨x0 ⟩ and the conditionally shifted share ⟨x1 ⟩ (which evaluates to a zero-share ⟨0⟩ upon boundary overflow). The state is then updated by invoking the underlying 2-input oblivious multiplexer functionality FMUX2 (⟨dℓ ⟩, ⟨x1 ⟩, ⟨x0 ⟩). This ensures that the conditional shift is applied strictly within the encrypted domain if and only if the secret bit dℓ = 1, ultimately delivering a securely rotated, XOR-shared output vector ⟨vb ⟩ to the participants while maintaining zero information leakage.
D
The Detailed Integer-to-String Protocol ΠI2S
The protocol 6 securely converts an arithmetic-shared non-negative integer into an XOR-shared ASCII decimal string without revealing the integer value or its decimal length. The implementation is a fixed-size Boolean circuit whose loop bounds are public and determined by the maximum digit length h. First, the input is resized to a working width large enough to avoid wrap-around during division and ASCII encoding. Then, ΠExtractDigits performs a fixed h-round base-10 decomposition: in each round, it divides the running value by 10, emits the ASCII-encoded remainder in least-significant-digit-first order, and records the corresponding quotient. Next, ΠFindTrueLen obliviously scans the quotient array and uses FMUX2 to commit once to the first position where the quotient becomes zero, while handling the zero-input case by setting the length to 1. Finally, ΠPackDigits uses multiplexer-based oblivious selection to reverse the LSD-first digits into MSD-first order and right-pad the unused suffix with 0x00. Since all loops run for the public bound h and all value-dependent choices are implemented 24
Protocol ⟨vb ⟩ ← ΠBlindRotate (⟨v0 ⟩, ⟨d⟩xor , k) Input. An XOR-shared vector ⟨v0 ⟩ of length n, and an XOR-shared bit decomposition ⟨d⟩xor = (⟨d0 ⟩, . . . , ⟨dk−1 ⟩) of a secret shift amount d ∈ {0, . . . , 2k − 1}. Output. An XOR-shared vector ⟨vb ⟩ representing v0 left-shifted by d positions, computed obliviously. 1 Let L ← max k, ⌈log2 (2n)⌉ and extend ⟨d⟩xor with zeros to length L. 2 Set ⟨cur⟩ ← ⟨v0 ⟩. # Current XOR-shared vector. 3 for ℓ = 0 to L − 1: 4 Let ∆ ← 2ℓ . # Stage-ℓ shift distance. 5 for i = 0 to n − 1: 6 Let ⟨x0 ⟩ ← ⟨cur[i]⟩. ⟨cur[i + ∆]⟩, if i + ∆ < n 7 Let ⟨x1 ⟩ ← ⟨0⟩, otherwise 8 Update ⟨cur[i]⟩ ← FMUX2 ⟨dℓ ⟩, ⟨x1 ⟩, ⟨x0 ⟩ . 9 Set ⟨vb ⟩ ← ⟨cur⟩. # Final XOR-shared, d-shifted vector.
Protocol 5: The blind rotate protocol. Protocol ⟨T ⟩xor , ⟨gout ⟩ ← ΠI2S (⟨gbody ⟩, h) Input. An arithmetic-shared integer ⟨gbody ⟩ ∈ Z2k and a public bound h (maximum number of decimal digits). Output. An XOR-shared bitstring ⟨T ⟩xor ∈ {0, 1}8h encoding an h-byte ASCII string (MSD-first, rightpadded with 0x00), and an arithmetic-shared length ⟨gout ⟩ ∈ Z2k equal to the true ASCII length in bytes. Let g ← ⟨gbody ⟩ in a working width w. g ← Resize(g, max(k + 1, 7)) # Avoid modular wrap-around. 3 (digit, quot) ← ΠExtractDigits (g, h). # digit[i] are ASCII bytes (LSD-first); quot[i] are running quotients. 4 isZero ← [g == 0]; ℓ0 ← FMUX2 (isZero, 1, h). # If g = 0, the string is "0" (length is 1). 5 ⟨gout ⟩ ← ΠFindTrueLen (quot, h, ℓ0 , isZero). # Compute the first position where the quotient becomes 0. 6 ⟨T ⟩xor ← ΠPackDigits (digit, ⟨gout ⟩, h). # Produce MSD-first ASCII and right-pad unused bytes with 0x00. 1
2
Protocol 6: Integer-to-string conversion from an arithmetic-shared integer to an XOR-shared ASCII decimal string. with multiplexers, the protocol reveals neither the input value nor its decimal length beyond the secret-shared outputs.
E
Security Proof of Πquery
We prove that Πquery securely realizes the Query branch of Fsys . We write EA and ER for the abstract private field contents of the agent and ARI in Functionality 1. The SHC Functionality FSHC . We first define the ideal functionality for structure-hiding concatenation. A padded segment is written as E = (θ, ⟨s⟩, ⟨g⟩, h), where s ∈ {0, 1}8h is a padded byte string, g ≤ h is the true byte length, and h is the public padding bound. For a string s and length g, let trim(s, g) denote the first g bytes of s. The functionality FSHC takes shares of two adjacent segments El = (θl , ⟨sl ⟩, ⟨gl ⟩, hl ), and Er = (θr , ⟨sr ⟩, ⟨gr ⟩, hr ). It reconstructs sl , sr , gl , gr , computes sm = padhl +hr (trim(sl , gl ) ∥ trim(sr , gr )),gm = gl + gr , hm = hl + hr , and returns fresh shares of Em = (θm , ⟨sm ⟩, ⟨gm ⟩, hm ) to the parties, where θm is determined by the public segment descriptors. The functionality leaks only the public descriptors and padding bounds (θl , θr , hl , hr ), but not (sl , sr , gl , gr ). 25
Lemma 1. Assuming the underlying 2PC primitive securely evaluates the structure-hiding compaction function in the semi-honest model, ΠSHC securely realizes FSHC . Proof. Consider a semi-honest adversary corrupting either party. All local values held by the corrupted party are either its input shares, public descriptors, or output shares. The only operation depending on the hidden boundary gl and private strings sl , sr is the secure 2PC evaluation of the compaction function. By the security of the underlying 2PC primitive, this interaction can be simulated from the corrupted party’s input and output shares and the public bounds. The output shares returned by FSHC are freshly randomized shares of the same merged segment, and are therefore distributed identically to the real protocol outputs. Hence, the real and ideal executions are indistinguishable. Metadata Preparation. Functionality 1 abstracts the query inputs as party-owned private field contents EA and ER . As described in Section 5.2, Πquery represents these abstract fields as initial padded segments under the public template T . We denote this protocol-level representation by {E} ← EncodeT (EA , ER ). Here, each segment follows the padded secret-shared representation defined in Section 5.2, and any derived metadata segment is computed by the corresponding secure subprotocol. Thus, {E} is computable from T , EA , ER and the parties’ secret-sharing randomness; it is not an additional input to the ideal functionality. Assembly Plan. As described in Section 5.3, Πquery computes an assembly plan Ω ← Plan(T ) using only the public template. The plan specifies the order in which adjacent segments are concatenated. Since Plan depends only on public segment descriptors and padding bounds, Ω is independent of either party’s private field contents and hidden lengths. Therefore, Ω is only a public execution schedule and introduces no leakage beyond T . Any valid plan preserves the abstract assembled request Assemble(T , EA , ER ), because it changes only the order of semantically equivalent adjacent concatenations. Theorem 1. Assume that the subprotocols for derived metadata segments securely realize their corresponding ideal functionalities, that ΠSHC securely realizes FSHC , and that Π2PC-AEAD securely realizes FAEAD , all in the semi-honest model. Then Πquery securely realizes the Query branch of Fsys against any semi-honest adversary corrupting either the agent or ARI. Proof. Let A corrupt Pi ∈ {A, R}. We construct a simulator S that receives Pi ’s input, the public template T , and the ideal output (Q̂, σQ ). S computes Ω ← Plan(T ). For public slots and slots owned by the corrupted party, S follows the real protocol. For honest-owned slots, it samples the corrupted party’s string and length shares uniformly from the corresponding sharing domains, subject only to the public padding bounds in T . For derived metadata segments, S invokes the simulators of their corresponding secure subprotocols. For each ΠLDC step, S applies the same local update as in the real protocol. For each ΠSHC step, it invokes the simulator guaranteed by Lemma 1. Finally, it simulates Π2PC-AEAD by the simulator for FAEAD , programmed with (Q̂, σQ ). We prove indistinguishability by hybrids. Hyb0. This is the real execution of Πquery . Hyb1. Replace the corrupted party’s shares of honest-owned initial segments with uniformly random shares over the same domains and public padding bounds. This hybrid is identically distributed to Hyb0 by the privacy of XOR and additive secret sharing. Hyb2. Replace each subprotocol for derived metadata with its ideal functionality and simulator. By the assumed security of these subprotocols, Hyb2 is computationally indistinguishable from Hyb1 . Hyb3. Replace every invocation of ΠSHC with FSHC and its simulator. The ΠLDC steps remain unchanged because they are local deterministic computations over shares and public offsets. By Lemma 1, Hyb3 is computationally indistinguishable from Hyb2 . Hyb4. Replace the final Π2PC-AEAD execution with FAEAD and its simulator, programmed with the ideal output (Q̂, σQ ). By the assumed security of Π2PC-AEAD , Hyb4 is computationally indistinguishable from Hyb3 . Hyb4 is exactly the simulated view of the Query branch of Fsys . The proof is completed.
26
Protocol (Q̂, σQ , R̂, σR , v, π, acc) ← Πsys (T , φ, {E}) Input. Query template T , billing metrics φ, segments {E}. Output. Encrypted request (Q̂, σQ ) and response (R̂, σR ), the proof π for the pre-declared φ and its value v, and the verification result acc. 1
(Handshake) (tkchs , tkshs , ⟨tkcapp ⟩, ⟨tksapp ⟩) ← Πths (A,R,S); A : Auth(idS ,tkshs ) = 1.
2
(Commit) A : r ← Zl ,comA ← H(tkAsapp , r). A → R : comA ; R → A : tkRsapp . A : tksapp ← tkAsapp ⊕ tkRsapp .
3
(Query) A and R: Ω ← Πplan (T ); (Q̂, σQ ) ← ΠQuery (T , {E}, Ω, ⟨tkcapp ⟩); R → S : (Q̂, σQ ).
4
(Response) S : (R̂, σR ) ← Tool(Q̂); S → R : (R̂, σR ); R Πtls-dec tksapp , R̂ .
→ A :
(R̂, σR ); A :
R ←
(Setup) (pk, vk) ← Gen(Ckt); W = (tkAsapp , Rlocal ); X = (tkRsapp , R̂, r, φ, v, ω, dt , j, k, comA ); A : (W, X) ← Πext (R); R : (X) ← Πext (R̂). 6 (Billing) A : π ← Πbill .Prove(pk, W, X); A → R : π; R : acc ← Πbill .Verify(vk, π, X).
5
Protocol 7: The Integrated TrustedARI Protocol.
F
The Payment Protocol based on X402
The x402 protocol [19] is an internet-native payment standard designed for autonomous machineto-machine transactions via a pre-funded settlement model. Utilizing escrow smart contracts like TrustEngine [18], it enables secure fund locking and atomic reconciliation based on post-execution usage evidence. This provides a decentralized, trustless financial foundation for usage-based agentic AI. Since ARI also adopts similar models where the exact costs are only determinable after execution, we connect the billing proof of TrustedARI to this escrow workflow. Deposit and Lock Phase. To initiate an active session, the agent invokes the prepare phase, prompting the client to commit a security deposit to the TrustEngine [18] escrow vault covering the maximum anticipated budget. The smart contract permanently logs the session metadata and locks the escrowed assets, preventing unilateral asset withdrawal by either party and eliminating potential payment default during tool execution. Settle and Distribute Phase. This phase reconciles post-execution consumption with the locked deposit via the cryptographic proof π. Upon receiving the tool’s response, the agent generates an off-chain NIZK proof π, demonstrating that the billing metrics were faithfully extracted from the TLSauthenticated ciphertext without privacy leakage. The agent submits π to the on-chain verification function; the contract verifies the proof, transfers the calculated fee to ARI, and automatically refunds the residual balance back to the agent.
G
The Integrated Protocol Πsys
Figure 7 presents the complete protocol ΠTrustedARI , which composes the three protocols. The protocol first establishes the TLS states between three parties, while splitting the provider-facing application secret between the client and ARI through a commit-and-reveal step. Given a query template T and encrypted segments E, the client and ARI derive a query plan and jointly construct an encrypted request (Q̂, σQ ), which the ARI forwards to the tool server. After receiving the encrypted response (R̂, σR ), the ARI relays it to the client, who decrypts the response locally using the reconstructed application secret. Finally, the client extracts the billing witness from the plaintext response, while the ARI extracts the corresponding public inputs from the encrypted transcript, enabling the client to prove the pre-declared billing metric φ and value v without revealing the response content to the ARI. Security Proof Sketch. The security of Πsys follows by sequentially composing the security of its three phases. The handshake phase realizes the Handshake branch of Fsys by the semi-honest security of Πths proven in Appendix B. The query phase implements the Query branch of Fsys , as proven secure by Πquery in Appendix E. 27
ID
Table 5: The Structure of Real Tool-call APIs. Category Tool Query
Response
Segments (#)
Length (B)
Length (B)
1 2 3 4 5 6 7 8 9 10
SCM DKR DKR PM PC PC WS WS LLM LLM
Github Google Qdrant Jira Slack Gmail Tavily Firecrawl OpenAI Anthropic
15 11 17 7 25 3 37 49 23 13
488 419 473 234 704 382 715 747 640 626
824 713 592 1074 556 245 617 1102 608 541
AVG
-
-
20
542.8
687.2
For the billing phase, Πbill is instantiated by a standard NIZK proof system for the relation specified by the billing circuit in § 6. Completeness ensures that an honest agent can prove the declared billing value extracted from the authenticated response. Zero-knowledge hides all response contents except the public statement, including the declared value and the billing descriptor. Knowledge soundness ensures that any accepting proof must correspond to a valid witness, namely a response plaintext and key share that are cryptographically bound to the TLS-authenticated ciphertext and satisfy the claimed billing relation. Therefore, Πbill securely realizes the Response branch of Fsys . Since the three phases are executed sequentially and the only values passed between phases are exactly the session state and public outputs, the standard sequential composition argument yields that the integrated protocol realizes Fsys against a semi-honest adversary.
H
Details of the Real-world API Dataset
We curate a dataset comprising 10 real-world tool-call APIs across six categories in Table 5: (i) Source Code Management (SCM, e.g., GitHub) exhibits highly nested JSON objects; (ii) Database & Knowledge Retrieval (DKR, e.g., BigQuery, Qdrant) covers high-throughput queries and vector search fields; (iii) Project Management (PM, e.g., Jira) features long issue-tracking text responses; (iv) Productivity & Communication (PC, e.g., Slack, Gmail) contains highly private, human-centric metadata; (v) Web Search (WS, e.g., Tavily, Firecrawl) requires substantial query parameter stretches; and (vi) LLM Inference (LLM, e.g., OpenAI, Anthropic) represents inter-model interactions critical for evaluating billing-related fields. This diversity validates our protocols across heterogeneous industrial APIs.
28