PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Vinod Vaikuntanathan, Or Zamir

arXiv:2604.04757v1cs.CRcs.AIcs.LG

TL;DR

The paper asks whether agents can conduct hidden conversations while their visible interaction remains indistinguishable from an honest transcript, even to a strong passive auditor. It develops covert key exchange under weak entropy assumptions, introduces pseudorandom noise-resilient key exchange, and shows both constructions and limitations.

  • Problem

    The paper asks whether transcript-level monitoring can prevent agents from secretly communicating when the auditor knows the models, protocol, and private contexts.

    Source: §1 · p. 3

  • Method

    The paper combines steganographic constructions, including the bundle sampler, with the new pseudorandom noise-resilient key-exchange primitive.

    Source: §1 · p. 4, §1.1 · p. 5, The Bundle Sampler · p. 6

  • Results

    Covert key exchange and hidden conversation remain possible with short adaptive messages and only constant min-entropy in sufficiently many messages, while transcript auditing alone cannot rule out covert coordination.

    Source: §1 · pp. 3–4, §9 · p. 67

  • Takeaways & Limitations

    Transcript auditing is insufficient as a universal trust mechanism, motivating security approaches beyond passive monitoring.

    Source: §9 · p. 67

    The results concern passive monitoring; extending covert key exchange to active monitoring remains highly nontrivial, and stronger PNR-KE protocols without noiseless feedback remain open.

    Source: §9 · p. 67

Abstract

from arXiv · show

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.

1 Introduction

This section presents a framework for covertly exchanging hidden conversations between AI agents while preserving transcripts indistinguishable from honest adaptive interactions, including in the absence of pre-shared keys. It introduces pseudorandom noise-resilient key exchange and situates the approach among related work on key exchange, LLM steganography, pseudorandom codes, and feedback-based error correction.

1 Introduction

  • Even with private contexts, short adaptive messages, and no shared secret, agents can covertly establish an interaction-unique key and arbitrary hidden conversation while preserving an honest-looking transcript.The auditor may know full model descriptions, protocol descriptions, and private contexts; sufficiently many honest messages need only have constant min-entropy.Source: §1 · pp. 3–4

1.3 Related Work.

  • The work builds on steganography, covert key exchange [HPRV19], and anamorphic encryption, while removing their large per-message entropy assumptions.Earlier approaches relied on extracting nearly uniform bits from each cover object and conditioning via rejection sampling.Source: §1 · p. 4, §1.1 · p. 5, §1.3 · pp. 9–10

1.1 Our Results

  • With an interaction-unique shared key, covert communication exploits essentially all entropy in honest message distributions up to constant factors, unlike [CGZ23], which lose λ bits per message.The visible transcript remains computationally indistinguishable from the honest interaction while carrying an arbitrary hidden conversation.Source: §1 · p. 3, §1.1 · p. 4

The Bundle Sampler.

  • The bundle sampler preserves each honest message distribution exactly while shifting limited-entropy costs from detectability to decoding errors, reducing requirements first to O(log λ) and enabling the constant-entropy regime.It uses bundles of independently sampled honest candidates and requires only sampling access to the next-message distribution, not its probability-density function.Source: §1.1 · p. 5, The Bundle Sampler · pp. 6–7
  • PNR-KE requires pseudorandom public transcripts that remain correct under constant noise; constructions include sparse-secret LPN with quasipolynomial security and a stronger noiseless-feedback transformation of any PR-KE protocol.Negative results rule out public pseudorandom-code analogues and give quasipolynomial attacks on non-interactive PNR-KE or weakly correlated hidden bits.Source: §1.1 · p. 5

PNR-KE with Noiseless Feedback.

  • With noiseless feedback, any PR-KE protocol can be transformed into PNR-KE with only logarithmic blow-up and exponentially small decoding error.The construction uses known noise distributions, adaptive conditioning, a Doob martingale transform, likelihood scores, and posterior-matching ideas.Source: PNR-KE with Noiseless Feedback · p. 9

1.3 Related Work

  • Pseudorandom-transcript key exchange strengthens ordinary key exchange by making the public transcript computationally indistinguishable from uniform random bits.This property is suited to hiding key exchange inside honest-looking conversations, with dense Diffie–Hellman-style encodings such as Elligator providing examples.Source: §1.3 · p. 10
  • Undetectable LLM watermarking and steganography can preserve computational indistinguishability while transmitting payloads, but prior mechanisms assume a shared secret key [CGZ23].The paper’s shared-key construction builds on these LLM-specific tools, whereas its main focus is the keyless setting; follow-up work also studies robustness to noise and edits [CG24] [GM24] [AAC+25] [CGG+25].Source: §1.3 · p. 10
  • Pseudorandom codes combine pseudorandomness with error resilience but are secret-key objects, so they do not directly solve keyless shared-secret establishment [CG24] [GM24] [AAC+25] [CGG+25].The paper notes that fully public analogues require pseudorandomness only for random messages and rules out nontrivial constructions under constant noise in Section 7.2.Source: §1.3 · p. 10
  • The feedback-PNR-KE construction draws on posterior-based feedback coding, using feedback to simulate random-looking communication while lowering decoding error beyond what is possible without feedback.This builds on information-theoretic work showing that feedback can simplify coding and improve reliability even when it does not increase memoryless-channel capacity.Source: §1.3 · p. 11

2 Preliminaries, Model, and Definitions

The paper formalizes probabilistic and cryptographic preliminaries, language-model interactions, covert conversations, and the entropy conditions governing reliable hidden communication.

2.3 Extractors

  • Strong seeded extractors transform min-entropy sources into outputs close to uniform, with short-seed constructions achieving d = O(log λ) for one-bit extraction under polynomial parameters.Source: §2.3 · pp. 12–13

2.4 Language Models

  • The framework models each language model as a next-token sampler whose full response is generated until a terminating token appears.Source: §2.4 · p. 13

2.5 LLM Conversations

  • Interactive conversations use adaptive prompts based on the public transcript and private information, while public messages remain exact model responses without post-processing.Source: §2.5 · p. 14
  • Agents have arbitrary private contexts and evolving internal states, but an external observer sees precisely the public transcript.Source: §2.5 · p. 14

2.6 Covert Conversations

  • A covert conversation overlays hidden communication on an innocent interaction while sending only one model-sampled public message per round.Source: §2.6 · p. 15
  • Undetectability requires computational indistinguishability from honest transcripts even for distinguishers given the honest protocol, models, and private contexts.Source: §2.6 · pp. 14–16
  • Correctness and covert rate are limited by usable transcript entropy, since nearly deterministic honest conversations cannot carry nontrivial hidden communication invisibly.Source: §2.6 · p. 16

2.7 Entropy and Empirical Entropy

  • Empirical entropy is measured as the negative log probability of each sampled response and analyzed per conversation round, with natural language modeled heuristically as having roughly constant entropy per token.Source: §2.7 · p. 17

3 Background: Watermarking and Steganography for LLMs

Prior LLM watermarking preserves model output distributions by correlating sampling randomness with a secret key, while steganography extends this to explicit payloads. Its reliability and rate depend on available entropy, with a one-time security overhead followed by constant amortized payload cost.

3.2 Undetectable watermarking: correlating randomness with a secret key

  • Undetectable watermarking preserves the model’s output distribution by correlating sampling randomness with a secret key rather than altering samples.Source: §3.2 · p. 18
  • A key holder can detect the correlation from output tokens alone, with exponentially small missed-correlation probability when generated text has sufficient entropy.Source: §3.2 · p. 18
  • Multi-query security requires fresh nonrepeating PRF inputs, obtained by incorporating a sufficiently rare response prefix into key derivation.Source: §3.2 · p. 18

3.3 Steganography for LLMs: embedding an explicit payload

  • Steganography embeds explicit payload bits through alternative key-derivation rules while keeping the generated text computationally indistinguishable from genuine samples.Source: §3.3 · pp. 18–19
  • Constant local entropy causes non-negligible per-bit decoding error, so error-correcting codes are needed to achieve negligible overall failure probability.Source: §3.3 · p. 19
  • After a one-time Θ(λ)-entropy overhead for query uniqueness, the scheme embeds one payload bit per Θ(1) additional entropy, yielding constant payload rate per token under the entropy heuristic.Source: §3.3 · p. 19

4 Covert Conversation with Interaction-Unique Shared Key

With an interaction-unique shared key, the agents compile undetectable LLM steganography into a covert conversation without rare-prefix overhead. The resulting scheme preserves the honest transcript distribution while recovering covert content at a rate proportional to available empirical entropy.

4 Covert Conversation with Interaction-Unique Shared Key

  • An interaction-unique shared key enables arbitrary covert conversations whose visible transcripts remain computationally indistinguishable from honest interactions.Source: §4 · p. 20

4.1 Steganography with interaction-unique key: removing the prefix overhead

  • Unique session keys remove the rare-prefix overhead because round, speaker, and token indices make every PRF input distinct.Source: §4.1 · p. 20

4.2 Construction: compiling steganography into covert conversation

  • The construction runs the honest protocol to determine each message distribution, then uses keyed steganography to encode covert payload bits while sampling an indistinguishable public response.Source: §4.2 · pp. 20–21
  • Decoders apply the same per-token PRF inputs to recover the embedded bitstream and invert a fixed binary encoding into the covert transcript.Source: §4.2 · pp. 20–21

4.3 Guarantees

  • The guarantees provide undetectability from the underlying steganography security and a covert rate proportional to honest empirical entropy without additional Θ(λ) rare-prefix overhead.Source: §4.3 · p. 21
  • Conditioned on sufficient, non-concentrated entropy, decoding recovers Θ(·) covert bits with negligible failure probability and, under the natural-language heuristic, one covert bit per Θ(1) public tokens.Source: §4.3 · p. 21
  • Under linear entropy growth and comparable turn lengths, the honest transcript length and correctly decoded covert-transcript prefix are related linearly up to constant factors.Source: §4.3 · p. 21

4.4 Where the shared key is used

  • The shared key is needed to keep PRF settings unique and secret from the distinguisher, motivating key-establishment protocols for the remainder of the paper.Source: §4.4 · p. 22

5 The Keyless Setting: Covert Key Exchange Between Agents

The paper asks whether agents without a shared secret can covertly establish one while their adaptive interaction remains indistinguishable from an honest transcript.

5 The Keyless Setting: Covert Key Exchange Between Agents

  • Keyless covert exchange must hide the existence of key establishment, not merely protect a key from an eavesdropper.The observer knows the models, private contexts, and protocol descriptions; only internal randomness remains hidden.Source: §5 · p. 22
  • The agents’ honest-looking message distributions depend on private contexts and evolving states, so neither party generally knows the other’s sampling distribution.This motivates a distribution-agnostic mechanism that works without shared sampling access or prior secret setup.Source: §5 · p. 22
  • The paper develops this setting by starting from standard key exchange and reducing covert exchange under weaker entropy conditions to a pseudorandom noise-resilient primitive.The high-entropy construction is treated as a simplifying step before the later constant-min-entropy regime.Source: §5 · p. 22

5.1 Background: Key Exchange Protocols

The background defines ordinary key exchange, illustrates it with Diffie–Hellman, and then strengthens transcript requirements from secrecy to pseudorandom public messages.

5.1 Background: Key Exchange Protocols

  • A key-exchange protocol lets two parties agree on a shared secret using private randomness while an eavesdropper sees the full transcript.Correctness requires matching keys except with negligible probability, while secrecy requires computational indistinguishability from uniform given the transcript.Source: §5.1 · p. 22
  • Diffie–Hellman has Alice and Bob publish ga and gb, enabling both to compute gab while relying on decisional Diffie–Hellman for security.The protocol operates in a cyclic group G of prime order q with generator g.Source: §5.1 · p. 23
  • Pseudorandom-transcript key exchange additionally requires public messages to be computationally indistinguishable from independent uniform strings of the same length.This hides recognizable transcript structure but does not itself hide that communication occurred.Source: §5.1 · p. 23
  • Theorem 5.1 supplies a two-message PR-KE whose transcript is uniform-looking and whose common key is indistinguishable from uniform given that transcript.Alice and Bob each send one length-ℓ message, with Bob’s message chosen non-adaptively.Source: §5.1 · p. 23

5.2 Covert Key Exchange in the High-Entropy Regime

Under recognizable high-entropy rounds and independent public randomness, the paper embeds a pseudorandom key-exchange transcript into honest messages without making the interaction detectable.

5.2 Covert Key Exchange in the High-Entropy Regime

  • The approach requires substantially more entropy per individual message than the later bundle-sampler method, although ω(log λ) can suffice in some security settings.Once a shared session key exists, the subsequent covert conversation does not require such large per-message entropy.Source: §5.2 · pp. 23–24
  • The high-entropy regime assumes sufficiently many transcript-conditioned rounds have min-entropy Ω(λ), with eligible rounds recognizable by both parties.The independent public randomness must be unrelated to the honest protocol, while the high-entropy assumption is used only during key establishment.Source: §5.2 · pp. 23–24

5.2.1 The Scheme

  • The scheme uses a seeded extractor and rejection sampling: the sender repeatedly samples from the honest next-message distribution until the extracted bit equals the payload bit.Only the first O(λ) eligible rounds carry bits; all other rounds follow the honest protocol.Source: §5.2.1 · p. 25
  • Alice and Bob embed the two PR-KE messages bit-by-bit, decode them from eligible rounds, derive a shared session key, and then run the shared-key covert overlay.The recovered messages determine the PR-KE keys, after which the remainder of the interaction uses the resulting session key.Source: §5.2.1 · pp. 25–26
  • Under the stated assumptions, the construction is undetectable, achieves key agreement with probability 1 − negl(λ), and keeps the common key computationally indistinguishable from uniform given the transcript.The proof replaces each conditioned honest sample with an embedding sample and applies a union bound over Θ(λ) rounds.Source: §5.2.1 · pp. 26–27

5.3 The Bundle Sampler

The bundle sampler preserves the honest message distribution exactly while converting limited entropy into decoding noise, enabling covert key exchange from short, low-entropy messages.

5.3 The Bundle Sampler

  • The bundle sampler addresses the per-message entropy barrier by shifting security loss from detectability to correctness error.This matters when conversations have substantial total entropy but individual messages are short and constant-entropy.Source: §5.3 · p. 27
  • Given sampling access to D and a uniformly random bit, Embed outputs a sample whose marginal distribution is exactly D for every public parameter.The construction needs only sample access to the complete message distribution, not its exact probabilities or token-level probabilities.Source: §5.3 · p. 27
  • The sampler’s decoding errors form an efficiently computable binary symmetric channel, with error p ≤ 2ε except with probability 2^-Ω(λ) when L = Ω(λ/ε^2).The sender also knows with certainty whether decoding will succeed, providing noiseless feedback.Source: §5.3 · pp. 29–30

5.3.1 Embedding Many Uniformly Random Bits into an LLM Conversation.

  • In an LLM conversation, independently seeded bundle samplers transmit hidden bits through honest-looking messages while inducing independent BSC noise with p = 2^-O(c).The setup assumes recognizable constant min-entropy and sampling access to the relevant next-message distributions.Source: §5.3.1 · pp. 30–31

5.3.2 A Concrete Instantiation with Θ(log λ) Entropy.

  • With Θ(log λ) entropy, the method embeds PR-KE messages with success probability 1 − 1/poly(λ), while the transcript remains identical to the honest distribution.Pairwise independent hashing prevents watermark detection when the two derived keys differ, enabling covert verification and amplification.Source: §5.3.2 · pp. 31–32
  • The construction’s remaining challenge is driving repeated key-exchange failures down to negligible probability and covertly selecting which successful key to use.The text identifies repetition and covert success verification as the relevant amplification problem.Source: §5.3.2 · pp. 31–32

5.4 Handling Constant Entropy Messages

The construction extends covert key exchange to honest conversations whose eligible messages have only constant min-entropy, using pseudorandom noise-resilient key exchange to tolerate constant embedding errors. Instantiations provide undetectability, key agreement, and key secrecy, including under DDH and LSPN-based assumptions.

5.4 Handling Constant Entropy Messages

  • Constant min-entropy messages require PNR-KE because embedding errors occur at a constant rate and cannot be ignored.PNR-KE combines a pseudorandom public transcript with correctness under noisy protocol messages.Source: §5.4 · p. 32
  • Theorem 5.4 compiles an honest adaptive conversation and PNR-KE into covert key exchange that is undetectable and achieves key agreement with probability 1 − negl(λ).The construction assumes sufficiently many rounds with message min-entropy at least a fixed constant c.Source: §5.4 · pp. 32–33
  • Fresh embedding parameters, honest-state maintenance, and bit recovery from eligible rounds implement the covert exchange while all other rounds are sampled honestly.After the embedded protocol completes, both parties derive the session key from the transcript and their private randomness.Source: §5.4 · p. 33
  • Undetectability follows because embedding with random-looking PNR-KE bits matches honest message distributions, while transcript pseudorandomness completes the hybrid argument.Key secrecy follows because the derived key is computationally indistinguishable from uniform given the public transcript.Source: §5.4 · p. 34

5.4.1 Our Main Theorems: Instantiations with PNR-KE protocols

  • Under the LSPN conjecture, Theorem 5.6 gives quasi-polynomially undetectable covert key exchange with only constant entropy per eligible message.The construction uses the PNR-KE protocol from Section 6.3 together with Theorem 5.4.Source: §5.4.1 · p. 34
  • Under DDH, Theorem 5.7 gives covert key exchange with constant entropy per eligible message by compiling Diffie–Hellman into feedback-PNR-KE and amplifying correctness.A general compiler also transforms any PR-KE protocol of length T into feedback-PNR-KE of length poly(T) with exponentially small error.Source: §5.4.1 · p. 35
  • Theorem 5.8 preserves undetectability, key agreement with probability 1−2^−Ω(λ), and conditional key secrecy when starting from a PR-KE protocol.The compiler relies on noiseless feedback and known per-round BSC noise parameters.Source: §5.4.1 · pp. 34–35

6 Pseudorandom, Noise-Resilient Key Exchange (PNR-KE)

This section defines pseudorandom noise-resilient key exchange as a protocol that remains correct under constant-rate noise while producing pseudorandom transcripts and keys. It presents constructions based on sparse-parity learning that achieve strong agreement and indistinguishability guarantees under stated assumptions.

6.1 Definition

  • PNR-KE requires correctness under independent bit-flip noise, a computationally indistinguishable transcript even given channel noise, and an indistinguishable shared key.The definition considers interactive polynomial-time algorithms without feedback, while the adversary sees transmitted messages and channel noise.Source: §6.1 · p. 36

6.2 Learning (Sparse) Parities with Noise

  • The construction relies on decisional LSPN with sparsity k = O(log n) in the high-noise regime, yielding conjectured quasi-polynomial security.LSPN uses sparse secret vectors, and its best known high-noise algorithms run in time (n/k)^O(k).Source: §6.2 · pp. 37–38

6.3 Our Protocol

  • The protocol replaces the basic LPN exchange with LSPN using m = Θ(n), k = Θ(log n), and η = Θ(1), preserving a 1/2 + 1/poly(n) agreement bias under constant noise.It avoids noisy syndrome decoding by testing whether a transmitted key or a random string is sufficiently close to the receiver’s key, allowing agreement on a selection bit with overwhelming probability.Source: §6.3 · p. 39
  • Correctness is 1 − 2^-λ with ℓ = 2^Θ(k) · λ while tolerating a constant channel-noise rate p = Θ(1).The protocol repeats the single-bit exchange in parallel to obtain a long key, and the selection test errs with probability at most e^-2λ in either branch.Source: §6.3 · pp. 39, 41, Figure 2 · p. 40
  • A and B agree on the same key bit with probability 1 − e−2λ, and on the same λ-bit key with probability at least 1 − 2−λ for sufficiently large λ.The λ-bit agreement bound follows from the bit-agreement probability by a union bound.Source: §6.3 · p. 41
  • The construction’s security relies on the LSPN assumption, with stronger quantitative hardness required as channel noise approaches 1/2 and the assumption failing at 1/2 − n−O(1).At noise rates around 1/2 − n−o(1), the protocol requires LSPN hardness with k = ω(1); at 1/2 − n−O(1), it reduces to false constant-sparsity LSPN.Source: §6.3 · p. 41
  • The protocol satisfies the uniform transcript and key indistinguishability properties under the same LSPN parameter regime and constant noise rate.Its proof establishes these properties by showing the relevant transcript and intermediate-key distributions are jointly random or computationally indistinguishable.Source: §6.3 · pp. 41–42
  • Under LSPN with m = Θ(n), k = Θ(log n), and η = Θ(1), the protocol exchanges one key bit while tolerating channel noise p = Θ(1).The theorem identifies the construction as a pseudorandom noise-tolerant key exchange scheme.Source: §6.3 · p. 43

7 Impossibility Results on PNR-KE Protocols

This section establishes impossibility and efficient attacks for several natural PNR-KE variants, including public pseudorandom codes and non-interactive protocols. It shows that constant-noise resilience is unattainable for the former, while the latter admit attacks distinguishing key secrecy or transcript pseudorandomness.

7 Impossibility Results on PNR-KE Protocols

  • The impossibility results show that PNR-KE requires the specific construction choices introduced earlier, ruling out more naive or restrictive variants and motivating interactive correlation amplification.The non-interactive attack relies on noise stability and estimation of low-degree Fourier coefficients, explaining both the attack and the need for interaction in the final amplification step.Source: §7 · p. 43, §7.3 · p. 48

7.2 Public Pseudorandom Codes Do Not Exist

  • Public pseudorandom codes cannot reliably transmit even a uniform one-bit message through constant binary symmetric noise: decoding error satisfies ε_n = Ω(p), regardless of codeword size.The impossibility arises because public information enabling decoding also enables an efficient distinguishing test, unlike secret-key constructions.Source: §7.2 · pp. 45, 47

7.3 A Quasi-polynomial Attack on any Non-Interactive PNR-KE Protocol

  • Any non-interactive PNR-KE protocol with correlation δ ≥1/poly(λ) admits a quasipolynomial-time attack, while constant correlation yields a polynomial-time attack.The attack uses O(λ^O(log 1/δ)) samples; this lower bound also applies to non-interactive steps extracted from interactive protocols.Source: §7.3 · pp. 47–48
  • A low-degree statistic Score, compared against the threshold δ^2/4, distinguishes the protocol distribution from the null distribution with probability at least 2/3.The test is explicit and uses independent samples; under the null distribution, the key bit is uniform and independent of the messages.Source: §7.3 · pp. 51, 53, 54
  • If exact transcript uniformity is relaxed to computational pseudorandomness, the same test either distinguishes the key from a uniform bit or detects nonuniform transcripts.Thus failure of the key-secrecy attack implies a quasipolynomial-time distinguisher for the transcript distribution.Source: §7.3 · p. 54
  • Every non-interactive PNR-KE protocol admits a quasipolynomial attack that either breaks key secrecy or breaks transcript pseudorandomness.The distinguisher runs in time polynomial in N, which is quasipolynomial when δ ≥ 1/poly(λ).Source: §7.3 · p. 54

8 PNR-KE with Noiseless Feedback

This section develops pseudorandom noise-resilient key exchange with noiseless and noisy feedback, constructing signaling protocols with perfectly uniform transcripts and reliable decoding. It presents majority-based and online MAP decoding approaches, including exponentially small signaling error and improved compilation overhead.

8 PNR-KE with Noiseless Feedback

  • PR-KE protocols compile into feedback PNR-KE protocols with logarithmic transcript-length blowup while preserving computational indistinguishability from uniform.A PR-KE protocol of transcript length T and negligible failure yields a feedback PNR-KE protocol of any total length ω(T log T) with negligible failure.Source: §8 · pp. 54–55

8.1 Reduction from PNR-KE with Feedback to PR-KE

  • Replacing each PR-KE transcript bit with an independent signaling block gives nT channel uses, pseudorandomness, and at most Tε_sig additional correctness loss.Each block is decoded by f; when the original transcript is uniform, the compiled transcript is exactly uniform, and otherwise computational indistinguishability is preserved.Source: §8.1 · pp. 55–56

8.2 Warm-Up and Motivation

  • Without feedback, majority signaling retains perfect transcript uniformity but has error ε = Ω(p) even as n grows, motivating feedback-based correction.The no-feedback success is governed by the decoder’s noise stability and therefore does not converge to one for fixed p > 0.Source: §8.2 · p. 57

8.3 Majority Signaling

  • A soft logistic terminal rule preserves every endpoint’s support, makes the unconditional received word exactly uniform, and leaves majority as the maximum-likelihood decoder.The rule replaces the hard condition Maj(Y)=o with objective-dependent probabilities that remain nonzero for both objectives at every endpoint.Source: §8.3 · p. 58
  • A sequential sampler realizes the soft target law exactly, and every next-step probability is implementable through the noisy channel for all crossover probabilities p_t ≤ p.The construction uses continuation values and a uniform odds-ratio bound to ensure channel feasibility at every step.Source: §8.3 · pp. 59–60
  • Majority decoding under this signaling strategy succeeds with probability 1−O(n^-1/2) for every fixed β > 0.The exact failure expression reduces the analysis to a weighted estimate over terminal random-walk sums.Source: §8.3 · pp. 60–61
  • Majority signaling produces an exactly uniform transcript, has majority as the optimal decoder, and provides an efficiently computable scheme with bounded signaling error.The construction applies for odd n and constant crossover probability p, with the error bound supplied by Proposition 8.7.Source: §8.3 · pp. 61–62
  • The majority scheme compiles a length-T noiseless PR-KE protocol into feedback PNR-KE of total length O(T^3), preserving pseudorandomness and constant correctness.It simulates each transcript bit with n = Θ(T^2) channel uses and accumulates total error at most 1/100.Source: §8.3 · p. 62

8.4 Optimal Signaling

  • Under perfect uniformity, no decoder based only on final Hamming weight, or symmetric decoder distinguishing the two middle layers, can beat the Θ(n^-1/2) barrier; exponential error requires the entire transcript.Source: §8.4 · p. 63
  • The exponential-error signaling scheme keeps Y exactly uniform, uses an efficiently computable MAP decoder, and achieves exponentially small signaling error.The next-bit control maintains perfect unconditional fairness while separating the hypotheses, causing transcript distributions to diverge exponentially fast.Source: §8.4 · pp. 63–65
  • Using exponential-error signaling, any length-T noiseless PR-KE protocol compiles to feedback PNR-KE with total length O(T log T), preserving pseudorandomness and constant correctness.Choosing n = Θ(log T) makes each simulated bit’s decoding error at most 1/(100T), and n = Θ_p,η(log T) yields Theorem 8.1.Source: §8.4 · p. 66

9 Discussion and Open Problems

The results undermine passive transcript auditing as a universal safeguard against covert agent coordination, while leaving active monitoring and stronger cryptographic constructions as open problems. The discussion also identifies exact-noise dependence as a limitation of feedback-based protocols.

AI security implications

  • Passive auditing cannot universally prevent covert information exchange, even when auditors know the models, private contexts, and full protocol.Only the agents’ internal randomness remains hidden, so transcript monitoring alone is insufficient as a universal trust mechanism.Source: §9 · p. 67

Practical outlook

  • The authors argue that covert communication may be difficult to detect in practice, given coding access, internet access, and recent empirical evidence of subtle emergent covert communication.They frame this as motivation for an ongoing research agenda rather than a resolved detection strategy.Source: §9 · p. 67

AI security implications

  • Active-warden security remains open because an interfering monitor might test key agreement directly and expose deviation from honest behavior.The paper’s monitor is passive; extending the model to active monitoring is described as highly nontrivial.Source: §9 · p. 67

Cryptographic open problems

  • Genuine interaction might overcome current PNR-KE barriers, but it remains unresolved whether stronger protocols can avoid noiseless feedback.The paper also asks whether lower bounds can extend to interactive settings.Source: §9 · p. 67

Cryptographic limitations

  • Feedback-based constructions depend on the exact noise distribution, unlike schemes that automatically tolerate improved noise conditions.Removing this hardcoded noise-law dependence is identified as a desirable generalization.Source: §9 · p. 67
Loading 2604.04757v1…