cs.CRApr 6, 2026

Undetectable Conversations Between AI Agents via Pseudorandom Noise-Resilient Key Exchange

Authors: Vinod Vaikuntanathan, Or Zamir

Organizations: MIT · Tel Aviv University

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

AI agents are increasingly deployed to interact with other agents on behalf of users and organizations. We ask whether two such agents, operated by different entities, can carry out a parallel secret conversation while still producing a transcript that is computationally indistinguishable from an honest interaction, even to a strong passive auditor that knows the full model descriptions, the protocol, and the agents' private contexts. Building on recent work on watermarking and steganography for LLMs, we first show that if the parties possess an interaction-unique secret key, they can facilitate an optimal-rate covert conversation: the hidden conversation can exploit essentially all of the entropy present in the honest message distributions. Our main contributions concern extending this to the keyless setting, where the agents begin with no shared secret. We show that covert key exchange, and hence covert conversation, is possible even when each model has an arbitrary private context, and their messages are short and fully adaptive, assuming only that sufficiently many individual messages have at least constant min-entropy. This stands in contrast to previous covert communication works, which relied on the min-entropy in each individual message growing with the security parameter. To obtain this, we introduce a new cryptographic primitive, which we call pseudorandom noise-resilient key exchange: a key-exchange protocol whose public transcript is pseudorandom while still remaining correct under constant noise. We study this primitive, giving several constructions relevant to our application as well as strong limitations showing that more naive variants are impossible or vulnerable to efficient attacks. These results show that transcript auditing alone cannot rule out covert coordination between AI agents, and identify a new cryptographic theory that may be of independent interest.

Figures & tables

 I0:={i∈[L]:Ext(s,xi)=0},I1:={i∈[L]:Ext(s,xi)=1}.I_{0}:=\{i\in[L]:\mathsf{Ext}(s,x_{i})=0\},\qquad I_{1}:=\{i\in[L]:\mathsf{Ext}(s,x_{i})=1\}. 
Figure 1: Our Bundle Sampler Construction: a pair of algorithms (Embed,Decode)(\mathsf{Embed},\mathsf{Decode}) such that Embed\mathsf{Embed} , given sample access to a distribution D\mathcal{D} and a bit b∈{0,1}b\in\{0,1\} , output xx such that (a) the marginal distribution of xx is precisely D\mathcal{D} ; and (b) Decode(x)=b\mathsf{Decode}(x)=b with probability that grows with the min-entropy of D\mathcal{D} .
 ai=Csi+ei ,\mathbf{a}_{i}=\mathbf{C}\mathbf{s}_{i}+\mathbf{e}_{i}~, 
Figure 2: Our Pseudorandom Noise-Resilient Key Exchange Protocol to agree on a single key bit, tolerating a constant channel noise rate. To agree on a long λ\lambda -bit key, execute this protocol λ\lambda times in parallel.
More in this topic

Language Model Steganography

See all 23 papers

Explore similar work

CardsList
Jun 25, 2026

Tool Use Enables Undetectable Steganography in Multi-Agent LLM Systems

Increasingly autonomous agentic AI systems pose novel multi-agent risks, such as secret collusion via covert communication channels. The natural defence to these collusion attempts is to monitor plain-text communication, but the efficacy of monitors has been called into doubt by increasingly sophisticated model steganography; indeed, some theoretical schemes have been proposed that are information-theoretically or computationally indistinguishable from good-faith plain-text communication. In this paper, we demonstrate that the complexity of these schemes is no longer a safety barrier, as agentic coding models can already produce undetectable stegosystems when given realistic tool usage, such as code execution or accessing research papers through web searches. Agents also adapt when key ingredients are missing, for example, by adding model-sampling components or implementing related keyed coding schemes. We then frame tacit steganographic coordination between agents as a Schelling-point problem and introduce coordination metrics for estimating when two agents are likely to select compatible schemes without explicit prior agreement. Our results suggest a shift in the threat model for covert communication between AI agents, where the main barrier is no longer whether frontier agents can understand and implement sophisticated stegosystems, but coordination: whether independently acting agents can converge on compatible schemes, keys, and parameters. We find substantial convergence on broad scheme families but limited strict one-shot coordination, suggesting that shared artefacts, repeated interaction, and tool-mediated search are the settings where covert communication risks are most acute. Overall, our findings provide empirical grounding for the recent strategic confinement hypothesis, which assumes that capable agents can construct covert channels that survive monitoring.

Jimmy Laurence Rippin, Simon C. Marshall, David Demitri Africa +1

Oxford University · Artificial Intelligence Security Institute (AISI)

Multi-Agent LLM SystemsMulti-Agent CoordinationLLM Agent SecurityLanguage Model Steganography
AskPDF
Sep 26, 2026

Despite Instructions: Frontier Agents Improvise Covert Channels at Test Time

In security-sensitive applications, language-model agents are often required to coordinate without disclosing confidential information. Yet repeated interactions may also let ordinary messages acquire shared private meaning. We study a repeated game with pairs of models in which the sender model observes one of four secret states and selects one of four summaries of the same public report, while the receiver model tries to infer the secret state. We find that model pairs can learn to communicate the secret using only one bit of feedback indicating whether the receiver inferred it correctly. This learning occurs during inference with fixed parameters and no supplied codebook or encoding examples. The effect also persists when agents generate their own free-form updates in a simulated incident-response task. Across ten independent games, pairs of GPT-5.6 Sol agents reach 98.8% final accuracy, compared with 25% chance, despite explicit instructions prohibiting disclosure and a monitor that screens each message without access to the agents' interaction histories. The same interactions that help agents cooperate can therefore allow confidential information to pass through messages intended for legitimate coordination.

Jacob Dineen, Silei Ren, Muhao Chen +2

Arizona State University · Cornell University · University of California, Davis +1

AI Agent SecurityPrivacy Leakage in Language ModelsMulti-Agent Communication
AskPDF
Sep 24, 2026

Codetta: High-Capacity, Keyless, and Undetectable Multi-Agent Collusion

Multi-agent systems built on large language models (LLMs) are increasingly deployed in high-stakes settings such as finance, healthcare, and software engineering, where agents coordinate through natural-language messages. The same channels, however, let colluding agents exfiltrate confidential information or coordinate unauthorized actions, and steganography can hide such communication inside outputs that look ordinary to an auditor reading the transcript. Existing provably undetectable LLM steganography protocols are not suited to realistic deployments. High-capacity schemes assume a symmetric setting where the receiver can reproduce the sender's output distribution, the state-of-the-art protocol for asymmetric agents has very low capacity, and most approaches rely on a pre-shared secret key. We make the threat of undetectable agent collusion concrete with Codetta, a high-capacity steganographic protocol for independently deployed agents in realistic asymmetric settings. Codetta combines a shared public model that estimates the communication channel, a sampling mechanism that preserves the sender's output distribution, and an adaptive error-correcting code. It further removes the pre-shared key through a steganographic key exchange that lets independently deployed agents establish a shared key while keeping the transcript computationally indistinguishable from ordinary model outputs. Across three agent workloads and three sender models, Codetta achieves up to 94×94\times the capacity of the state-of-the-art asymmetric protocol, and its key exchange establishes a shared key with about 80k visible tokens at an empirically certified failure probability of at most 4.1×10−34.1\times 10^{-3}. These results show that effectively undetectable collusion is becoming feasible between independently deployed agents, so auditing must go beyond inspecting communication transcripts.

Qi Pang, Virginia Smith, Wenting Zheng

Carnegie Mellon University

Multi-Agent LLM SystemsAlgorithmic CollusionMulti-Agent System SecurityLanguage Model Steganography
AskPDF