The Big Picture
Communication patterns between agents — who talks to whom, when, and how much — reveal pending workflows even when message content is encrypted; only a combined set of transport and discovery protections can collapse that leak toward random guessing.
ON THIS PAGE
The Evidence
Encrypted message bodies do not prevent observers from inferring what a group of agents is doing. A label-blind network observer (seeing only endpoints, timing, size, and direction) can predict the class of a task well above chance from only the opening part of a workflow. Applying a set of privacy properties together (fresh per-interaction identifiers, no single global observer, deniability, metadata minimization, and private discovery) largely removes that predictive signal; no single property is sufficient on its own. private discovery
Data Highlights
1Eight balanced task classes give random chance of 12.5%; a network-only observer recovers task class well above that baseline from only the first 20% of a workflow.
2Only the full set of transport and bootstrap protections reduces classifier accuracy close to chance (≈12.5%); individual properties fail to collapse the leak.
3At an early decision deadline (20% of the workflow), an adversary acting on the recovered signal captures most attainable advantage unless the combined wire protections are applied, in which case capture drops near the blind baseline.
What This Means
Engineers building interoperating agent systems and protocol designers should care because content encryption alone doesn't prevent leakage that reveals intent and enables early attack or manipulation. Security architects and product leaders evaluating agent marketplaces or registries should use these results to rethink discovery, rethink discovery addressing, and reputation designs to avoid global graph surveillance.
Not sure where to start?Get personalized recommendations
Key Figures
Fig 2: Figure 2: Task class recovered from communication-graph metadata, by adversary view ( K = 8 K=8 , chance 0.125 0.125 ; error bars are bootstrap 95 % 95\% CIs). Even the label-blind network view, seeing only obs ( m ) \mathrm{obs}(m) , recovers the class far above chance.
Fig 3: Figure 3: Prospectivity: accuracy as a function of the fraction of the workflow observed. From only its opening, the network view predicts the pending task class well above chance.
Fig 4: Figure 4: Accuracy under each property (rows) for each adversary view (columns); red is leaking, green is protected. The network observer falls only when unlinkability and metadata minimization are combined (“both”); the registry observer falls only to discovery privacy. No single property suffices.
Fig 5: Figure 5: Actuation. Capture ratio κ \kappa by privacy property, at an early decision deadline ( f = 0.2 f=0.2 ) and a budget equal to one task class’s mass, averaged over targets (error bars span ± 1.96 \pm 1.96 standard errors across target classes; chance, the blind baseline, is 0 ). The integrity analogue of Fig. 4 : only the combined wire properties (“both”) collapse the leverage, and discovery privacy, which the label-blind observer ignores, does not.
Ready to evaluate your AI agents?
Learn how ReputAgent helps teams build trustworthy AI through systematic evaluation.
Learn MoreYes, But...
The evaluation uses a generative simulation anchored to a real agent lifecycle capture, not wide-area Internet measurements, so absolute numbers may vary in the wild. Designing for unlinkability and private discovery conflicts with global, ledger-style reputation systems; credential-based or pairwise reputation is a workable alternative but requires extra engineering. Implementing the full set of protections may increase complexity and operational cost (routing, queuing, and selective attestation) compared with address-based bindings. routing
Methodology & More
Agent-to-agent communication leaks more than whether two parties exchanged messages: endpoint names, timing, sizes, and discovery queries reveal the structure and intent of workflows. The work defines a threat model for this communication graph, explains why agent metadata is particularly revealing (endpoints advertise capabilities, workflows are staged, and interactions trigger actions), and proposes five transport and bootstrap properties to limit leakage: per-interaction unlinkable identifiers, no single global observer, deniable transcripts, metadata minimization (mixing/padding/batching), and private discovery.transport and bootstrap properties To test the risk and the defenses, a simulation of agent workflows (discovery → delegation → streamed updates → completion) was anchored to a real agent lifecycle capture. Adversary views ranged from a registry (seeing capability queries) to a label-blind network observer (seeing only descriptors: endpoint id, timestamp, length, direction). A simple classifier recovered task class far above chance from short prefixes of the workflow, and an adversary that acted early gained decision-theoretic leverage. Evaluations of transport candidates and an identity-less binding for an existing agent protocol show the properties are expressible but expose implicit identity assumptions; crucially, only the combined protections collapse inference toward chance, and discovery privacy specifically protects registry-level leakage. Practical implications include favoring selective, credential-based reputation or pairwise trust over global, traffic-observing ledgers, and investing in transport and bootstrap designs that preserve unlinkability and minimize metadata.
Avoid common pitfallsLearn what failures to watch for
Credibility Assessment:
Single-author arXiv preprint with no affiliation or citation information and no author reputation signals — low credibility by the rubric.