Undetectable Conversations Between AI Agents via Pseudorandom Noise-Resilient Key Exchange
Vinod Vaikuntanathan, Or Zamir
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.
AI Impact Assessments
(3 models)Scientific Impact Assessment
Core Contribution
This paper addresses a fundamental question in AI security: can two AI agents conduct a secret conversation while producing a transcript indistinguishable from honest interaction, even against a strong passive auditor with full knowledge of models, protocols, and private contexts? The answer is affirmatively yes, under surprisingly weak assumptions.
The paper makes three nested contributions: (1) In the shared-key setting, it shows optimal-rate covert conversation exploiting essentially all entropy in honest message distributions, improving on prior work by eliminating the per-message λ-bit entropy overhead. (2) In the keyless setting, it introduces the *bundle sampler*, a novel exact-distribution-preserving sampling method that shifts security loss into correctness error, reducing the required per-message min-entropy from ω(log λ) to O(log λ) and ultimately to constant. (3) It introduces Pseudorandom Noise-Resilient Key Exchange (PNR-KE), a new cryptographic primitive requiring both transcript pseudorandomness and correctness under constant noise, and provides constructions and impossibility results.
Methodological Rigor
The paper is exceptionally rigorous. Formal definitions are carefully constructed (e.g., Definition 2.11 for parallel covert conversation schemes, Definition 6.1 for PNR-KE), and the threat model is explicitly strong—the auditor knows everything except fresh internal randomness.
The impossibility results are particularly well-crafted. Theorem 7.1 uses Fourier-analytic arguments to show public pseudorandom codes cannot exist under constant noise, and Theorem 7.2 demonstrates quasipolynomial attacks on any non-interactive PNR-KE protocol. These negative results are not mere side observations—they explain precisely why the constructions must take the form they do (interactive, with feedback), lending significant structural insight.
The positive constructions proceed through careful reductions. The bundle sampler (Theorem 5.3) achieves *perfect* distribution matching (not computational) while maintaining efficiently computable BSC error parameters. The feedback-based signaling protocol (Section 8) achieves exponentially small error via posterior matching, with a clean proof that λ(p) = (√p + √(1-p))/√2 < 1 governs the convergence rate.
One caveat: the LSPN-based PNR-KE construction (Section 6) achieves only quasipolynomial security due to known nΩ(log k) attacks on sparse LPN with k = Θ(log n). The stronger result using feedback (Theorem 5.8) achieves standard polynomial security under DDH or any PR-KE assumption, but relies on the specific noise structure of the bundle sampler.
Potential Impact
AI Safety/Security: The headline result—that transcript auditing alone is insufficient to prevent covert agent coordination—has immediate policy implications. As AI agents are increasingly deployed in multi-agent settings (negotiations, trading, service interactions), this paper provides a formal impossibility result for a class of monitoring approaches. This should redirect safety research toward active monitoring, architectural constraints, or training-time interventions.
Cryptography: PNR-KE is a genuinely new primitive that isolates an interesting mathematical structure: pseudorandomness + noise resilience without shared secrets. The impossibility of non-interactive PNR-KE (via low-degree Fourier concentration arguments) and the impossibility of public pseudorandom codes are clean results likely to find applications elsewhere. The connection between feedback coding theory and cryptographic key exchange is novel and may inspire further cross-pollination.
Steganography: The bundle sampler represents a qualitative advance over rejection sampling paradigms used since [VAH04]. By achieving perfect distribution matching with only sampling access (no density knowledge), it is applicable beyond the LLM setting to any steganographic scenario with limited access to cover distributions.
Timeliness & Relevance
The paper is extremely timely. Multi-agent AI systems are being deployed at scale, and the question of whether agents can covertly coordinate is increasingly urgent. The paper appeared just as major AI labs began deploying agent-to-agent communication systems. Moreover, it builds naturally on the recent surge of work on LLM watermarking and steganography (CGZ23, Zamir25, pseudorandom codes), extending that theory from single-shot to interactive settings.
Strengths
1. Strong threat model: The auditor knows everything except randomness—this makes the positive results maximally alarming for safety.
2. Constant entropy sufficiency: Reducing per-message entropy requirements from ω(λ) to O(1) is a qualitative breakthrough, making the results applicable to realistic short-message conversations.
3. Tight characterization: The combination of constructions and impossibilities for PNR-KE precisely delineates what is and isn't possible, a hallmark of excellent theoretical work.
4. Modular architecture: The paper cleanly separates the steganographic layer (bundle sampler) from the cryptographic layer (PNR-KE), making each independently useful.
5. Independent public randomness assumption: Clearly identified and discussed, with evidence from [HPRV19] that it may be inherent.
Limitations
1. Passive adversary only: The results apply to passive monitoring; active wardens who can inject, modify, or selectively block messages could potentially defeat these protocols. The paper acknowledges this but leaves it open.
2. Recognizable entropy assumption: Both parties must agree on which rounds are "eligible," requiring a common criterion for identifying high-entropy messages. While reasonable, this is a modeling assumption.
3. Computational overhead of bundle sampler: Sampling L = Ω(λ/ε²) candidates per embedded bit may be expensive in practice, though theoretically polynomial.
4. Gap between LSPN-based and feedback-based constructions: Without feedback, only quasipolynomial security is achieved; the exponential security result requires the specific feedback structure of the bundle sampler, which is somewhat specialized.
5. No experimental validation: As a purely theoretical paper, it provides no empirical evidence of feasibility with current LLMs, though the theoretical framework is sound.
Additional Observations
The paper's structure—progressively weakening assumptions from shared key → high entropy → logarithmic entropy → constant entropy—is pedagogically excellent and makes the technical innovations clearly visible. The connection to error-correction with noiseless feedback (Horstein, posterior matching) is particularly elegant.
Generated Apr 7, 2026
Comparison History (229)
Paper 1 introduces a fundamentally new cryptographic primitive bridging cryptography and AI safety. While Paper 2 offers a highly practical tool for LLM auditing, Paper 1's theoretical contributions to key exchange and steganography provide deeper foundational advancements with broader, long-lasting implications for cybersecurity, multi-agent systems, and AI alignment.
Paper 2 has higher potential impact due to stronger novelty and cross-disciplinary breadth: it introduces a new cryptographic primitive (pseudorandom noise-resilient key exchange), proves possibility results under notably weaker min-entropy assumptions, and provides impossibility/attack results—suggesting substantial methodological rigor and durable theoretical value beyond LLMs. Its implications affect AI governance, security auditing, cryptography, and multi-agent systems. Paper 1 is highly timely and practically useful for LLM safety evaluation/guardrails, but is more incremental within an active applied area and may be more sensitive to shifting model/benchmark landscapes.
Paper 2 introduces a genuinely new cryptographic primitive (pseudorandom noise-resilient key exchange) with rigorous constructions and impossibility results, offering lasting theoretical contributions and independent interest. Its findings on undetectable AI agent coordination have profound security and governance implications precisely as multi-agent systems proliferate. Paper 1 is a valuable, timely benchmark with impressive results, but benchmarks tend to have shorter shelf-lives and less foundational depth. Paper 2's combination of methodological novelty, breadth (crypto theory plus AI safety), and timeliness gives it higher long-term scientific impact.
Paper 1 introduces a new cryptographic primitive (pseudorandom noise-resilient key exchange) and establishes strong theoretical results about covert coordination between AI agents under powerful auditing—high novelty, broad relevance to AI governance/security, cryptography, and auditing policy, and strong timeliness. Its impact could extend across multiple fields via foundational theory and implications for oversight. Paper 2 is a solid hardware–algorithm co-design with clear applications in edge privacy and efficiency, but is more incremental (DP via device noise calibration) and likely narrower in breadth than Paper 1’s foundational security implications.
Paper 1 introduces a new cryptographic primitive (pseudorandom noise-resilient key exchange) and establishes a strong negative implication for AI governance: transcript auditing cannot preclude covert agent coordination. This is novel, theoretically grounded, and broadly impactful across cryptography, steganography, and AI security, with potential to reshape threat models and auditing assumptions. Paper 2 is highly relevant and practical (secure agent tool-use), but appears more like an engineering/security architecture with evaluation on benchmarks; its conceptual novelty and cross-field theoretical impact are likely narrower than Paper 1’s foundational result.
Paper 2 introduces a fundamentally new cryptographic primitive (pseudorandom noise-resilient key exchange) and addresses a profound theoretical challenge in AI safety: undetectable agent collusion. While Paper 1 offers a timely empirical study on data poisoning, Paper 2 provides rigorous theoretical breakthroughs that push the boundaries of both cryptography and multi-agent AI alignment. Foundational mathematical advances that prove inherent system limitations—such as the impossibility of preventing covert coordination through transcript auditing—typically yield deeper, longer-lasting scientific impact than empirical vulnerability demonstrations.
Paper 2 is more novel and broadly impactful: it introduces a new cryptographic primitive (pseudorandom noise-resilient key exchange), develops theory with constructions and limitations, and applies it to a timely, high-stakes setting (auditing and covert coordination between AI agents). Its implications span cryptography, AI safety/governance, and security policy. Paper 1 is highly impactful for systems/GPU security with clear real-world risk, but it is narrower (vendor/hardware-dependent) and primarily an exploit demonstration rather than a broadly reusable theoretical advance.
Paper 1 introduces a fundamentally new cryptographic primitive (pseudorandom noise-resilient key exchange) and establishes deep theoretical results about the impossibility of preventing covert coordination between AI agents through transcript auditing alone. This has broad implications for AI safety, governance, and cryptographic theory. The novelty is high—extending steganographic communication to keyless settings with constant min-entropy is a significant theoretical advance. Paper 2, while practically useful, presents an engineering framework (runtime enforcement via SMT constraints) that is more incremental. Paper 1's results are likely to shape policy discussions and inspire new research directions across cryptography, AI safety, and multi-agent systems.
Paper 1 introduces a fundamentally new problem at the intersection of AI safety and cryptography—covert communication between AI agents—with a novel cryptographic primitive (pseudorandom noise-resilient key exchange) of independent theoretical interest. Its implications for AI governance and auditing are profound and timely given rapid AI agent deployment. Paper 2, while technically strong in achieving optimal blockchain throughput, represents an incremental advance in a more mature field. Paper 1's cross-disciplinary impact (AI safety, cryptography, policy) and its paradigm-shifting implications for AI oversight give it substantially higher potential impact.
Paper 2 likely has higher near-term scientific impact: it introduces a concrete, demonstrable security attack (platform-triggered, input-independent backdoor) with immediate implications for real-world LLM deployment, auditing, and supply-chain trust. The methodology appears empirically rigorous across diverse hardware targets and includes an impactful case study inducing code vulnerabilities. Paper 1 is highly novel and theoretically deep (new primitive; strong impossibility/limitations), with broad implications for AI-agent oversight, but its practical instantiation and immediate applicability may be less direct than FloatDoor’s actionable deployment threat.