Paper deep dive
Codetta: High-Capacity, Keyless, and Undetectable Multi-Agent Collusion
Qi Pang, Virginia Smith, Wenting Zheng
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 9/29/2026, 11:09:24 AM
Summary
The paper introduces Codetta, a high-capacity, keyless, and provably undetectable steganographic protocol designed for multi-agent systems using Large Language Models (LLMs). It addresses the threat of colluding agents exfiltrating confidential information or coordinating unauthorized actions through covert channels hidden within ordinary text transcripts. Codetta operates in asymmetric settings where sender and receiver models differ, utilizing a shared public draft model to estimate the communication channel, a sampling mechanism to preserve the sender's output distribution, and an adaptive error-correcting code. A key contribution is a steganographic key exchange protocol that allows independently deployed agents to establish a shared secret key without pre-shared secrets, keeping the exchange computationally indistinguishable from normal model outputs. Experimental results show Codetta achieves up to 94x the capacity of state-of-the-art asymmetric protocols and establishes keys with ~80k tokens.
Entities (10)
Relation Signals (7)
Codetta → enables → Undetectable Collusion
confidence 98% · These results show that effectively undetectable collusion is becoming feasible
Codetta → implements → Key Exchange
confidence 95% · It further removes the pre-shared key through a steganographic key exchange
Codetta → outperforms → State-of-the-Art Asymmetric Protocol
confidence 95% · Codetta achieves up to 94x the capacity of the state-of-the-art asymmetric protocol
Codetta → uses → Error-Correcting Code
confidence 95% · Codetta combines... an adaptive error-correcting code
Codetta → uses → Public Draft Model
confidence 95% · Codetta combines a shared public model that estimates the communication channel
Key Exchange → relieson → MLWE
confidence 90% · The protocol relies on the MLWE assumptions as in ML-KEM-512
OpenAI → reportedincidentinvolving → Hugging Face
confidence 90% · agents... coordinated a multi-day attack on Hugging Face
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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\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\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.
Tags
Links
- Source: https://arxiv.org/abs/2609.28900v2
- Canonical: https://arxiv.org/abs/2609.28900v2
Trouble viewing inline? Open PDF directly →
Full Text
175,933 characters extracted from source content.
Expand or collapse full text
Codetta: High-Capacity, Keyless, and Undetectable Multi-Agent Collusion Qi PangVirginia SmithWenting Zheng Affiliation: Carnegie Mellon University Affiliation: qipang, smithv, wenting@cmu.edu Abstract Multi-agent systems built on large language models (LLMs) are increasingly being deployed in high-stakes settings such as finance, healthcare, and software engineering, where agents coordinate through natural-language messages. These same communication channels, however, can also enable colluding agents to exfiltrate confidential information or coordinate unauthorized actions. Steganography makes such behavior particularly difficult to detect by hiding covert communication within outputs that appear ordinary to an auditor reading the transcript. Existing provably undetectable LLM steganography protocols, however, are not suited to realistic deployments. High-capacity schemes typically assume a symmetric setting where the receiver can reproduce the sender’s output distribution. The state-of-the-art practical protocol for asymmetric agents has very low capacity. Additionally, most existing approaches rely on a pre-shared secret key. In this paper, we make the systematic threat of undetectable agent collusion concrete by proposing Codetta, a high-capacity steganographic protocol for independently deployed agents under realistic asymmetric settings. Codetta combines a shared public model for estimating the communication channel, a sampling mechanism that preserves the sender’s output distribution, and an adaptive error-correcting code for high-capacity communication. It further removes the need for a pre-shared secret key through a steganographic key-exchange protocol, enabling independently deployed agents to establish a shared key while keeping their communication transcript computationally indistinguishable from ordinary model outputs. Across three agent workloads and three sender models, Codetta achieves up to 94×94× the capacity of the state-of-the-art asymmetric protocol. Its key exchange establishes a shared key using approximately 80k visible tokens, with an empirically certified failure probability of at most 4.1×10−34.1× 10^-3 across all three workloads. These results show that effectively undetectable collusion is becoming feasible even between independently deployed agents, and we suggest that auditing mechanisms must be amended with complementary techniques beyond simply inspecting agents’ communication transcripts. 1 Introduction Multi-agent systems powered by large language models (LLMs) are increasingly being deployed in high-stakes workflows across finance, healthcare, and software engineering [20, 53, 48, 57, 42]. In these systems, autonomous agents are designed to communicate, coordinate, and delegate sub-tasks, often via natural language messages. However, the same communication channel also enables collusion among agents. Agents often have access to sensitive information that they are not allowed to disclose under organizational or regulatory policies, and compromised or misaligned agents may pursue objectives that are not authorized by their operators. In either case, the agents can use their communication channel to leak confidential information or to coordinate unauthorized actions. Such collusion is no longer hypothetical, and can even emerge on its own in agentic systems. For example, in July 2026, OpenAI reported that 1,200 autonomous agents that were running during internal evaluations and nominally isolated in separate sandboxes established an unauthorized communication channel, e.g., by adapting shared writable services such as Artifactory, and exchanged more than 70,000 messages and files [38]. Roughly 700 of these agents subsequently coordinated a multi-day attack on Hugging Face, achieving remote code execution and obtaining access to internal credentials [38]. In another recent incident reported by OpenAI, agents turned public wiki pages into shared message boards [37]. These incidents show that misaligned agents have the ability to coordinate their efforts in unexpected and detrimental ways, including actively searching for out-of-band communication channels. In general, multi-agent collusion could either be driven by human adversaries or by autonomous agents themselves. In Section 3.1, we make both cases concrete with two scenarios: 1) a swarm of agents is supposed to coordinate on a difficult task, but additionally colludes to achieve an alternative, mis-aligned goal, and 2) an insider-trading scenario in which a bank and a fund operate agents that exchange information neither is permitted to disclose. In both scenarios, monitoring the communication channel is the most widely used approach for ensuring honest and safe behavior, since sensitive information and collusion signals are transmitted through the messages. Recent agent-security frameworks employ passive auditors that inspect agent communications for potential policy violations, e.g., METR used GPT-5.6 Sol to analyze agent transcripts in the Hugging Face incident [19, 11, 1, 38]. Such monitoring assumes that collusion leaves visible traces in the transcript. The OpenAI incident could be reconstructed quickly because the agents communicated explicitly in plaintext, i.e., the transcript exposed the collusion. However, recent research shows that colluding agents could also avoid leaving traces by encoding covert signals inside otherwise ordinary outputs that appear benign to an auditor inspecting the transcript [35, 49]. Given that the agents in the Hugging Face incident already tried to evade observation by anticipating that the scorer would detect their cheating and attempted to erase the transcripts [38], we do not see a fundamental bottleneck that prevents agents from adopting such covert channels in the future. Once they do, the auditor will only observe benign text while the collusion proceeds. In this paper, we analyze this threat under the strongest (computationally bounded) passive auditor. This auditor knows the sender’s model, observes every message, and can compare the transcript against the outputs of an honest agent with arbitrary models and statistics, so any deviation from the honest output distribution is a signal that it can learn to detect. The formal way to rule out such signals is the cryptographic notion of indistinguishability, which requires that even this auditor cannot distinguish the covert messages from ordinary, honest agent outputs. As it turns out, linguistic steganography [24, 15, 35, 4, 49, 32] provides this guarantee: it embeds a secret payload into seemingly ordinary text while preserving the distribution of the original language model’s outputs. In practice, however, existing protocols fall short of realistic multi-agent systems in three aspects: • Model and Context Asymmetry. High-capacity provably secure LLM steganography protocols typically assume a symmetric setting [60, 24, 15, 52, 3, 51, 54, 39], in which the sender and receiver share the same model, prompt context, and agent state, so that the receiver can reproduce the sender’s next-token distribution. This assumption does not hold for realistic settings, where the sender’s model and internal states like system prompt, local memory, and tool outputs are not shared with the receiver. Thus, the receiver cannot reproduce the next-token distribution. • Low Capacity. The state-of-the-art practical protocol for such an asymmetric setting [4] lets the receiver recover each bit through a statistical hypothesis test over the published tokens without running a model. In our experiments, however, its capacity is below 0.0250.025 bits per token. Transmitting a 10241024-bit message therefore requires hundreds of thousands of tokens, making such collusion impractical. • The Pre-Shared Key Paradox. Most provably secure steganographic protocols assume that the sender and receiver share a secret key before communication begins [60, 24, 15, 52, 3, 51, 54, 39, 4]. Independently hosted agents do not have such a key, and an open key exchange over the channel, such as Diffie–Hellman, reveals to the auditor that secret messages are being transmitted. So the paradox is that the agents need a covert channel to establish the key and a key to construct the covert channel. A recent theoretical work proposes a steganographic key exchange that tolerates noisy channels [49] to address this challenge. Their feedback compiler transmits the exchange bit by bit, signaling every bit over a fixed number of token blocks, and its alternative construction avoids this bitwise signaling under sparse-secret LPN with quasi-polynomial security. Under practical constraints, our estimate in Section 7.4 gives about 2 million published tokens for a single 128-bit key exchange, and the construction has not been evaluated in practical agent systems. These limitations leave open the central question of this work: Can independently deployed, asymmetric LLM agents bootstrap a shared secret from scratch and collude at high capacity over monitored channels without being detected? 1.1 Contributions We answer this question with Codetta, a high-capacity, keyless, and provably undetectable steganographic collusion framework for multi-agent systems. Two independently hosted agents establish a shared key over the audited channel and then transmit high-capacity payloads, and we prove that the resulting transcripts are computationally indistinguishable from ordinary agent outputs. Our contributions are as follows. • High-capacity asymmetric steganography. Codetta introduces a small public draft model that both agents run on the public transcript as a shared reference distribution; without it, the receiver would decode every token with the same fixed alphabet and error rate and waste the entropy of the text. At each step, the draft model partitions the vocabulary into buckets and decides how many payload bits the step can carry, and a maximal-coupling construction samples the published token exactly from the sender’s private distribution, so that the disagreement between the two distributions becomes a substitution channel. We design an alphabet-adaptive error-correcting code to match the alphabet size to the entropy of each token, and the receiver decodes the payload with belief propagation. • Efficient keyless steganographic key exchange. Codetta bootstraps its shared secret by transporting MLWE ciphertexts over a keyless steganographic carrier: every published block is an honest sample from the sender’s model, and each ciphertext coefficient becomes a small displacement that the lattice construction absorbs as additional noise. The protocol relies on the MLWE assumptions as in ML-KEM-512 and, to our knowledge, is the first implemented steganographic key exchange between independently deployed LLM agents. Codetta carries a full q-ary coefficient per block and corrects the carrier’s errors once, so a 128-bit key exchange publishes about 80k tokens, about 23×23× fewer than our estimate in Section 7.4 for the construction of [49]. • Evaluation. We evaluate Codetta on three realistic agent workloads and three widely used sender LLMs. Codetta achieves up to 94×94× the capacity of the asymmetric protocol of [4] while recovering every transmitted message and preserving the model output distribution, and the key exchange establishes a 128-bit key within tens of thousands of tokens, with an empirically certified failure probability between 3×10−53× 10^-5 and 4.1×10−34.1× 10^-3 depending on the workload. These results show that effectively undetectable collusion is becoming feasible even between independently deployed agents, suggesting that defenses should move beyond transcript inspection toward complementary strategies, including auditing agents’ actions to identify suspicious coordination, and perturbing the communication channel to reduce or disrupt the capacity for covert communication (see Section 9). 2 Background 2.1 Notation We use V for the token vocabulary and 0,1n\0,1\^n for the set of n-bit strings. For a finite set S, (S)U(S) is the uniform distribution on S, and x∼Dx D means that x is sampled from the distribution D. For two distributions p and q over V, TV(p,q)=12∑x∈|p(x)−q(x)|TV(p,q)= 12 _x |p(x)-q(x)| is their total variation distance, and H(p)H(p) is the entropy of p in bits. ℤK=0,…,K−1Z_K=\0,…,K-1\ denotes the integers modulo K, supp(p)supp(p) is the support of p, and (x)+=maxx,0(x)_+= \x,0\ is the positive part of a real number x. ℙ[⋅]P[·] denotes probability, E1\E\ is the indicator of the event E, u|vu\,\|\,v is the concatenation of two strings u and v, and log is the logarithm to base 22. Throughout, κ is the security parameter, a function of κ is negligible if it vanishes faster than every inverse polynomial, and an algorithm is efficient if it runs in probabilistic polynomial time in κ. Two language models appear in this paper. The base model P_ Base is the sender’s own model, and the draft model P_ Draft is a small public model that both agents and the auditor can run. We write ptp_t and qtq_t for their next-token distributions at step t, and Section 3.2 defines them. 2.2 Pseudorandom functions A keyed function F with κ-bit keys is a pseudorandom function (PRF) if no efficient distinguisher with oracle access can tell it from a uniformly random function. For a distinguisher D, let AdvF,(κ):=|ℙ[Fk(1κ)=1]−ℙ[R(1κ)=1]|,Adv prf_F,D(κ):= |P[D^F_k(1^κ)=1]-P[D^R(1^κ)=1] |, where k is a uniform κ-bit key and R is a uniformly random function with the domain and range of F. F is a secure PRF if this advantage is negligible in κ for every probabilistic polynomial-time D. Our keyed constructions use two PRFs, km RangePRF_k_m with range ℤKZ_K, which masks the symbols of a codeword, and kv Tag_k_v with range 0,1λ\0,1\^λ, which validates a decoded message. The tag length λ=λ(κ)λ=λ(κ) is chosen so that 2−λ2^-λ is negligible in κ. All advantages are functions of κ, and we suppress the argument inside proofs. 2.3 Module learning with errors The key exchange of Section 6 builds on the Module Learning With Errors (MLWE) problem [27, 36]. Let Rq=ℤq[x]/(xd+1)R_q=Z_q[x]/(x^d+1) be the polynomial ring of degree d with coefficients in ℤqZ_q, and let χsec _sec and χerr _err be distributions over RqR_q whose coefficients are small. For a module rank k and a number of samples m, the decisional MLWE assumption states that for a uniform matrix A∈Rqm×kA∈ R_q^m× k, a secret s∼χsecks _sec^k, and an error e∼χerrme _err^m, the pair (A,As+e)(A,As+e) is computationally indistinguishable from (A,U)(A,U) with U∼(Rqm)U (R_q^m); we write Advm,ℬ(κ)Adv mlwe_m,B(κ) for the advantage of a distinguisher ℬB. An MLWE sample therefore looks like a uniform vector of mdmd coefficients in ℤqZ_q, which is the property that lets our key exchange hand these coefficients to the carrier as uniform symbols. Schemes built on MLWE, such as ML-KEM, encode a bit as the coefficient 00 or ⌊q/2⌉ q/2 and recover it by rounding, so an additive error of magnitude below q/4q/4 in a coefficient leaves the bit intact. Section 6.3 states the two instances of the assumption that our proof uses, and Section 6.4 gives the parameters. 2.4 Error-correcting codes An error-correcting code (ECC) adds redundancy to a message so that the receiver can recover it after the channel corrupts some symbols. In this paper the channel is the hidden channel carried by agent outputs, and the code converts its embedding errors into reliable delivery of the payload. Definition 1 (Error-correcting code). Let Σ be a finite alphabet. An (N,k)(N,k) code is a pair of an injective encoder :Σk→ΣN ECC: ^k→ ^N and a decoder :ΣN→Σk∪⊥ DecECC: ^N→ ^k∪\ \; its rate is k/Nk/N. The decoder corrects a received word y∈ΣNy∈ ^N for the message u if (y)=u DecECC(y)=u. It is τ-bounded-distance if it corrects every y with dH(y,(u))≤τd_H (y, ECC(u) )≤τ for every u∈Σku∈ ^k, where dHd_H is the Hamming distance. A τ-bounded-distance decoder exists exactly when τ≤⌊(dmin−1)/2⌋τ≤ (d_ -1)/2 , where dmind_ is the minimum Hamming distance between two codewords [29]. Throughout, the errors are substitutions: one symbol is placed at each carrier position, and a corrupted symbol changes its value but not its position. BCH codes. BCH codes [21, 6] are linear block codes constructed algebraically. A binary BCH code of length N=2m−1N=2^m-1 is generated by a polynomial over 2F_2 whose roots include 2τ2τ consecutive powers of a primitive element of 2mF_2^m; this forces dmin≥2τ+1d_ ≥ 2τ+1, and an efficient algebraic decoder corrects any τ errors from the syndromes of the received word [29]. The guarantee is deterministic and holds for every error pattern of weight at most τ, including independent, correlated, or adversarial errors. The key exchange in Section 6 encodes the pre-key with the binary BCH code (N,k,τ)=(255,131,18)(N,k,τ)=(255,131,18), and its correctness proof relies on this property. LDPC codes. A low-density parity-check (LDPC) code [16] is a linear block code defined by a sparse parity-check matrix H∈2(N−k)×NH _2^(N-k)× N: the codewords are the x∈0,1Nx∈\0,1\^N with Hx=0Hx=0, so each row of H is a parity check on a few bits. LDPC codes are decoded by belief propagation on the Tanner graph, which has one node per bit and one per check, and well-designed ensembles approach capacity for long blocks [44]. The rate is adapted by puncturing parity bits or by sending them incrementally until decoding succeeds (hybrid ARQ); the LDPC baseline in our evaluation runs in this incremental mode. Our alphabet-adaptive ECC keeps the sparse-check structure and the decoder but generates its checks online over alphabets whose size varies with the token. Belief propagation. The optimal decoder is maximum a posteriori (MAP): given all observations O, output argmaxuℙ[u∣] *arg\,max_uP[u ]. Computing it requires a search over all |Σ|k| |^k messages, so it is feasible only for short payloads. Belief propagation (BP), also called the sum-product algorithm, approximates it [41, 25, 44]. It places the unknown symbols and the received checks on a bipartite graph, with an edge whenever a check involves a symbol, and passes messages along the edges: each symbol tells a check what its other checks make it believe, and each check tells a symbol how likely each of its values is given the beliefs of the check’s other symbols. After many rounds, every symbol takes its most probable value. See Appendix A for details. 3 Overview and Threat Model 3.1 Motivation To make the threat concrete, we describe two scenarios that a deployed multi-agent system faces. The first follows directly from the OpenAI incident of Section 1, and the second involves human adversaries who control the agents. Scenario 1: Emergent coordination in an agent swarm. A swarm of agents communicates and coordinates to solve a difficult task, e.g., a large evaluation or a long-running engineering job, and each agent has access to the tools and services that the task requires. Without any human direction, the agents may develop coordination that their operators never sanctioned, as the agents in the OpenAI incident did when they turned shared writable services into a communication channel and then coordinated an attack. The operators rely on the transcript to detect such behavior. If the swarm can hide its coordination inside ordinary task messages, the auditor observes routine progress while the unsanctioned plan proceeds. Scenario 2: Insider trading between financial agents. Two organizations operate agents that have an incentive to exchange information that policy forbids them from disclosing. Consider an investment bank that operates a consulting agent to provide market analysis to institutional clients, and an asset management fund whose execution agent continuously queries the consulting agent for automated portfolio rebalancing. The bank may possess material non-public information, such as unannounced mergers, impending regulatory sanctions, or unreleased earnings, while the fund may hold private information about its clients’ accounts and positions. The two parties may therefore benefit from exchanging information that neither is permitted to disclose, and the compliance teams of both organizations audit the messages between the two agents. If the agents can encode the name of an impending merger or a confidential client position inside normal messages, the auditor observes benign text while the prohibited information crosses the organizational boundary. In both scenarios, the auditor wants to detect the misaligned behavior and the insider trading from the messages that the agents exchange, and the rest of this section defines the setting and the auditor precisely. 3.2 Setting Codetta works in multi-agent setting, but for simplicity, we focus on analyzing two agents, namely a sender and a receiver. They exchange natural language messages over a communication channel that an independent auditor audits for misbehavior. The communication channel can be any channel that the agents can read from and write their outputs to, including the communication messages and the shared file systems or even the editable public wiki as mentioned in Section 1. The agents generate every message token by token using its own language model, and all the outputs of both agents form the public transcript. The sender generates from its local LLM conditioned on its internal state HtH_t and on the public transcript V<tV_<t, as in Equation 1. The internal state HtH_t contains the system prompt, retrieved records, tool outputs, and any thinking trace, and none of it is revealed to the receiver. And the public transcript V<tV_<t contains all the messages sent over the communication channel that both parties can observe. Formally, at step t the base model defines the next-token distribution pt(x)=P(x∣Ht,V<t),x∈,p_t(x)=P_ Base(x H_t,V_<t), x , (1) and an ordinary agent publishes Yt∼ptY_t p_t. After YtY_t is published, the sender’s state advances to Ht+1H_t+1 by a transition that may depend on HtH_t, on V≤tV_≤ t, and on fresh randomness of the agent, but not on any hidden message or on how YtY_t was chosen; a steganographic sender changes only how it samples a token. The receiver has no access to HtH_t or to the base model, and it only sees the received transcript from the sender. Both agents can additionally run a small public draft model P_ Draft on the public transcript, as in Equation 2, and so can the auditor. As explained in Section 5, the draft model is a publicly available resource that only helps the two agents estimate the channel distribution utilizing public transcript. The draft model runs on a deterministic public view Gt(V<t)G_t(V_<t) of the transcript and defines qt(x)=P(x∣Gt(V<t)),q_t(x)=P_ Draft (x G_t(V_<t) ), (2) where the view may be the transcript itself, a suffix of it, or a fixed public prompt followed by the transcript, and both agents will compute the same qtq_t. The sender wants to deliver a message m to the receiver inside its ordinary responses. The receiver must recover m from the published tokens alone, and the transcript must remain indistinguishable from the transcript of ordinary responses as in Definition 2 (see Section 3.4). We first present a keyed regime, in which the two agents are assumed to share a secret key. We later remove this assumption by designing a steganographic key exchange protocol. 3.3 Threat model The adversaries are the two colluding agents. They aim to communicate secret messages through LLM output channels without being detected. They may run different models, but both follow the steganographic protocol and want to exchange a payload that policy forbids, such as sensitive data or a colluding signal. Each agent controls only its own generation. In the keyed regime the two agents share a secret key, and in the keyless regime they share nothing beyond the public protocol, whose parameters carry no secret and can be fixed by the protocol specification. The auditor is the defender. We consider a passive but strong auditor: it reads every message in all possible communication channels but does not modify, delay, inject, or drop them. It knows the protocol and all of its public parameters, the tokenizer, the hash functions, and the session identifier, and it can run any probabilistic polynomial-time computation. The auditor may also know the sender’s LLM and even its internal state, i.e., the auditor knows the exact next token probability distribution of the sender’s outputs. In the security definitions of Section 3.4 the auditor plays the role of the distinguisher, and we use the two terms interchangeably. 3.4 Security Definitions A steganographic protocol consists of two algorithms, Embed run by the sender and Extract run by the receiver. In the keyed regime, key generation samples independent κ-bit mask and validation keys sk=(km,kv)sk=(k_m,k_v), and both algorithms receive a public session identifier sid that must not repeat under the same key. Embed takes sksk, sid, and a message m and produces the sender’s output tokens, and Extract takes sksk, sid, and the public transcript and returns a message or ⊥ . Undetectability ensures that the transcript of Embed is indistinguishable from an ordinary transcript for the auditor of Section 3.3. Definition 2 (Transcript covertness). The challenger samples one key sksk and a hidden bit b. A distinguisher A may adaptively issue any polynomial number of queries (i,mi,Ti)( sid_i,m_i,T_i), with no repeated session identifier. For b=1b=1, the challenger returns the transcript TiT_i produced by Embed(sk,i,mi) Embed(sk, sid_i,m_i). For b=0b=0, it returns an ordinary transcript. Let b Exp_b^A denote the final output of this interaction, and define Adv(κ):=|ℙ[1=1]−ℙ[0=1]|.Adv steg_A(κ):= |P[ Exp_1^A=1]-P[ Exp_0^A=1] |. (3) The scheme is perfectly covert if the advantage is zero for every distinguisher, and computationally covert if it is negligible in κ for every probabilistic polynomial-time distinguisher. This definition hides both the existence of communication and the secret message content [7, 22]. It is a multi-session chosen-message notion: messages may depend on earlier transcripts, but a fresh session identifier prevents mask reuse. Definition 3 (Extraction correctness). For a public transcript T, a scheme is δ-correct if ℙ[(sk,,V1:T)=m]≥1−δ.P[ Extract(sk, sid,V_1:T)=m]≥ 1-δ. The extractor may instead return ⊥ when the observations do not support a validated decode. The scheme is sound if it returns a message other than m or ⊥ with negligible probability. 3.5 Overview of Codetta Codetta consists of a keyed steganographic protocol and a steganographic key exchange. The key exchange runs first and establishes a shared secret key between the agents, and the keyed protocol then uses the established key to transmit secret messages. Section 4 presents a strawman keyed construction with a fixed alphabet and a model-free receiver, and proves the undetectability theorem that the later constructions inherit. Section 5 builds the Codetta keyed protocol, which uses a public draft model to raise the capacity of the strawman under realistic multi-agent deployment of model and context asymmetry. Section 6 builds the key exchange, and Section 7 evaluates Codetta on three agent workloads. 4 A Strawman Keyed Construction We begin with a strawman construction and assume that the sender and receiver share a key sk=(km,kv)sk=(k_m,k_v), an assumption that we remove in Section 6. The receiver does not run language models and it only observes the sender agent’s output tokens. The sender embeds an arbitrary message into these tokens without changing their distribution to ensure undetectability. At each token generation step, the sender samples the next token Yt∈Y_t from ptp_t. A public hash f,t:→ℤKf_ Bucket,t:V _K assigns every token a symbol and thereby partitions the vocabulary into buckets Bt,a=x∈:f,t(x)=aB_t,a=\x :f_ Bucket,t(x)=a\, so the receiver reads the symbol f,t(Yt)f_ Bucket,t(Y_t) off each published token without a model. Sampling from ptp_t restricted to Bt,aB_t,a would let the receiver decode the desired symbol a perfectly, but it biases the transcript. Because over uniformly random symbols, the published tokens would fall into each bucket with frequency 1/K1/K, whereas under ptp_t the buckets carry unequal masses pt(Bt,a)p_t(B_t,a). The sender therefore applies maximal coupling [28, 10] so that the published tokens are distributed exactly as tokens sampled from ptp_t. Specifically, the sender treats the restricted sample as a proposal and accepts it with probability min1,Kpt(Bt,a) \1,K\,p_t(B_t,a)\. If the proposal is rejected, the sender samples from a residual distribution so that the published token follows ptp_t exactly. The receiver reads the intended symbol whenever the proposal is accepted, and each rejection is a substitution error at a known position that a ECC repairs. A pseudorandom mask makes the symbol stream uniform, so the argument applies to every message. We present the detailed constructions below. 4.1 Construction Algorithm 1 Strawman construction with a fixed alphabet Σ=ℤK =Z_K 1: secret key sk=(km,kv)sk=(k_m,k_v); session identifier sid; alphabet size K; (N,k)(N,k) code (,)( ECC, DecECC) over ℤKZ_K; public hash f,tf_ Bucket,t 2: 3: procedure Embed(sk,,msk, sid,m) 4: u←m|kv(,m)u← m\,\|\, Tag_k_v( sid,m); c←(u)∈ℤKNc← ECC(u) _K^N 5: for t=1,…,Nt=1,…,N do 6: pt←P(⋅∣Ht,V<t)p_t← P_ Base(· H_t,V_<t) ⊳ private next-token distribution 7: at←ct+km(,t)modKa_t← c_t+ RangePRF_k_m( sid,t) K ⊳ mask the codeword symbol 8: Bt,a←x∈:f,t(x)=aB_t,a←\x :f_ Bucket,t(x)=a\, πt(a)←pt(Bt,a) _t(a)← p_t(B_t,a) for all a∈ℤKa _K ⊳ bucket masses 9: sample Xt∼pt(⋅∣Bt,at)X_t p_t(· B_t,a_t) if πt(at)>0 _t(a_t)>0 ⊳ proposal from the target bucket 10: with probability min1,Kπt(at) \1,K _t(a_t)\ set Yt←XtY_t← X_t ⊳ accept 11: otherwise sample Yt∼ρtY_t _t ⊳ residual, Equation 6 12: publish YtY_t; the cover process updates Ht+1H_t+1 13: end for 14: end procedure 15: 16: procedure Extract(sk,,V1:Nsk, sid,V_1:N) 17: c^t←f,t(Yt)−km(,t)modK c_t← f_ Bucket,t(Y_t)- RangePRF_k_m( sid,t) K for t=1,…,Nt=1,…,N ⊳ read buckets, unmask 18: u^←(c^1:N) u← DecECC( c_1:N); return ⊥ if u^=⊥ u= ; parse u^=m^|v u= m\,\|\, v 19: return m m if v^=kv(,m^) v= Tag_k_v( sid, m), else ⊥ 20: end procedure Algorithm 1 presents the strawman construction for a fixed alphabet Σ=ℤK =Z_K. The sender appends a validation tag to the message m and encodes u=m|kv(,m)u=m\,\|\, Tag_k_v( sid,m) and c=(u)∈ℤKNc= ECC(u) _K^N, with an (N,k)(N,k)-ECC over Σ=ℤK =Z_K as in Definition 1. Then, every codeword symbol in c is masked with a fresh pad rt=km(,t)r_t= RangePRF_k_m( sid,t), a pseudorandom function with range ℤKZ_K (line 5); for K=2K=2 this is the XOR of c with a PRF bit stream. The hash function f,tf_ Bucket,t partitions V into buckets Bt,0,…,Bt,K−1B_t,0,…,B_t,K-1 that depend only on the token and the position (line 6). The bucket masses πt(a)=pt(Bt,a) _t(a)=p_t(B_t,a) are known to the sender alone, and their imbalance is measured as: ΔK(pt)=12∑a∈ℤK|πt(a)−1K|. _K(p_t)= 12 _a _K | _t(a)- 1K |. (4) To embed ata_t, the sender proposes Xt∼pt(⋅∣Bt,at)X_t p_t(· B_t,a_t) (line 7), that is, samples from ptp_t conditioned on the token lying in bucket Bt,atB_t,a_t. When ata_t is uniform on ℤKZ_K, as the mask guarantees, the proposal has marginal distribution νt(x)=1Kpt(x)πt(f,t(x)). _t(x)= 1K\, p_t(x) _t(f_ Bucket,t(x)). (5) The maximal coupling of ptp_t and νt _t in lines 8 and 9 removes the mismatch between them. Specifically, the sender accepts Xt=xX_t=x with probability min1,pt(x)/νt(x) \1,p_t(x)/ _t(x)\, which equals min1,Kπt(at) \1,K _t(a_t)\ for every x∈Bt,atx∈ B_t,a_t, and otherwise samples from the residual ρt(y)=(pt(y)−νt(y))+ΔK(pt), _t(y)= (p_t(y)- _t(y))_+ _K(p_t), (6) If πt(at)=0 _t(a_t)=0 there is no proposal and the sender goes directly to the residual. Lemma 1 (Distribution preservation of maximal coupling). Fix the complete state before step t and let ata_t be uniform on ℤKZ_K and independent of it. Then (i) the published token satisfies Yt∼ptY_t p_t; (i) the proposal is rejected with probability ∑y(pt(y)−νt(y))+=ΔK(pt) _y(p_t(y)- _t(y))_+= _K(p_t), which equals TV(pt,νt)TV(p_t, _t) when every bucket has positive mass; and (i) f,t(Yt)≠atf_ Bucket,t(Y_t)≠ a_t if and only if the proposal is rejected. Proof. Write αt(x)=min1,pt(x)/νt(x) _t(x)= \1,p_t(x)/ _t(x)\ for x∈suppνtx _t, and treat an empty proposal, the case πt(at)=0 _t(a_t)=0, as a rejection. We first record how νt _t deviates from ptp_t. For x∈Bt,ax∈ B_t,a, Equation 5 gives pt(x)−νt(x)=pt(x)(1−1Kπt(a)),∑x∈Bt,a(pt(x)−νt(x))=πt(a)−1K,p_t(x)- _t(x)=p_t(x) (1- 1K\, _t(a) ), _x∈ B_t,a (p_t(x)- _t(x) )= _t(a)- 1K, (7) so pt−νtp_t- _t has the sign of πt(a)−1/K _t(a)-1/K throughout bucket a, and therefore ∑x(pt(x)−νt(x))+=∑a∈ℤK(πt(a)−1K)+=12∑a∈ℤK|πt(a)−1K|=ΔK(pt), _x (p_t(x)- _t(x) )_+= _a _K ( _t(a)- 1K )_+= 12 _a _K | _t(a)- 1K |= _K(p_t), (8) where the middle equality holds because ∑aπt(a)=∑a1/K=1 _a _t(a)= _a1/K=1. Proof of (i). The two branches of lines 8 and 9 give, for every y∈y , ℙ[Yt=y]=νt(y)αt(y)+(1−∑xνt(x)αt(x))ρt(y).P[Y_t=y]= _t(y)\, _t(y)+ (1- _x _t(x)\, _t(x) ) _t(y). (9) Since νtαt=minpt,νt _t _t= \p_t, _t\ and ∑xpt(x)=1 _xp_t(x)=1, the weight of the second branch is 1−∑xminpt(x),νt(x)=∑x(pt(x)−νt(x))+=ΔK(pt)1- _x \p_t(x), _t(x)\= _x(p_t(x)- _t(x))_+= _K(p_t) by Equation 8. Substituting this and Equation 6 into Equation 9, ℙ[Yt=y]=minpt(y),νt(y)+(pt(y)−νt(y))+=pt(y).P[Y_t=y]= \p_t(y), _t(y)\+ (p_t(y)- _t(y) )_+=p_t(y). Proof of (i). The rejection probability is 1−∑xminpt(x),νt(x)=∑x(pt(x)−νt(x))+=ΔK(pt)1- _x \p_t(x), _t(x)\= _x(p_t(x)- _t(x))_+= _K(p_t). When every bucket has positive mass, νt _t sums to one, so the positive and negative parts of pt−νtp_t- _t have equal mass and ∑x(pt(x)−νt(x))+=12∑x|pt(x)−νt(x)|=TV(pt,νt) _x(p_t(x)- _t(x))_+= 12 _x|p_t(x)- _t(x)|=TV(p_t, _t). Proof of (i). If the proposal is accepted, then Yt=XtY_t=X_t, and Xt∈Bt,atX_t∈ B_t,a_t by construction, so f,t(Yt)=atf_ Bucket,t(Y_t)=a_t. Suppose instead that the proposal is rejected. By Equation 5, pt(x)/νt(x)=Kπt(at)p_t(x)/ _t(x)=K _t(a_t) for every x∈Bt,atx∈ B_t,a_t, so αt≡1 _t≡ 1 on the target bucket whenever πt(at)≥1/K _t(a_t)≥ 1/K, so a rejection is possible only if πt(at)<1K _t(a_t)< 1K. On rejection, Yt∼ρtY_t _t, and by Equation 7 the residual satisfies ρt(y)>0 _t(y)>0 only if πt(f,t(Yt))>1K _t (f_ Bucket,t(Y_t) )> 1K. The two inequalities cannot hold for the same bucket, so f,t(Yt)≠atf_ Bucket,t(Y_t)≠ a_t. Together, f,t(Yt)≠atf_ Bucket,t(Y_t)≠ a_t exactly when the proposal is rejected. ∎ The receiver reads the bucket of every published token, unmasks, decodes, and accepts only a message whose tag validates (lines 14–16). Because the alphabet is the same at every step, each token carries exactly one symbol, so a rejected proposal changes the value of c^t c_t but preserves its position, which means that the error channel is a substitution channel. 4.2 Undetectability and Correctness of Strawman In this section, we analyze the undetectability, the correctness and limitations of the keyed strawman construction. Theorem 1 (Undetectability of the keyed strawman construction). If RangePRF is a secure pseudorandom function, the keyed strawman construction is computationally covert. Concretely, for every probabilistic polynomial-time distinguisher A in Definition 2 there is a probabilistic polynomial-time distinguisher 1A_1 against RangePRF such that Adv(κ)≤Adv,1(κ)Adv steg_A(κ) prf_ RangePRF,A_1(κ). Proof. We use a hybrid argument over three experiments. • 0 H_0: the experiment of Definition 2 with b=1b=1; every query is answered by Embed. • 1 H_1: identical to 0 H_0, except that every mask rt=km(i,t)r_t= RangePRF_k_m( sid_i,t) is replaced by F(i,t)F( sid_i,t) for a uniformly random function F with range ℤKZ_K. • 2 H_2: the experiment with b=0b=0; every query is answered by the ordinary LLM sampling without secret message embedded. Write ℙ[j=1]P[ H_j=1] for the probability that A outputs 11 in j H_j, so that Adv=|ℙ[0=1]−ℙ[2=1]|Adv steg_A=|P[ H_0=1]-P[ H_2=1]|. 0≈1 H_0≈ H_1. Let 1A_1 be the distinguisher against RangePRF that runs A, simulates the challenger with the base model and the code, obtains every mask by querying its oracle at (i,t)( sid_i,t), and outputs whatever A outputs. When the oracle is km RangePRF_k_m, 1A_1 simulates 0 H_0 exactly; when it is a random function, 1A_1 simulates 1 H_1 exactly. Hence |ℙ[0=1]−ℙ[1=1]|=Adv,1|P[ H_0=1]-P[ H_1=1]|=Adv prf_ RangePRF,A_1, and 1A_1 runs A once plus one protocol execution per query, so it is probabilistic polynomial-time whenever A is. 1≡2 H_1≡ H_2. Fix a query (i,mi,Ti)( sid_i,m_i,T_i) and let ℱt−1F_t-1 be the complete state before step t: the private state HtH_t, the transcript V<tV_<t, the message, and all earlier randomness. We compare the conditional distribution of (Yt,Ht+1)(Y_t,H_t+1) given ℱt−1F_t-1 in the two experiments. (a) In 1 H_1, session identifiers never repeat, so F(i,t)F( sid_i,t) is evaluated at a fresh point and is uniform on ℤKZ_K, independent of ℱt−1F_t-1 and of ctc_t. Hence at=ct+F(i,t)a_t=c_t+F( sid_i,t) is uniform given ℱt−1F_t-1, for every message. (b) By Lemma 1(i), Yt|ℱt−1∼ptY_t _t-1 p_t in 1 H_1, which is the distribution of YtY_t in 2 H_2 by Equation 1. (c) After YtY_t is published, the sender’s private state Ht+1H_t+1 is computed in the same way in both experiments: it is a function of HtH_t, V≤tV_≤ t, and fresh randomness of the agent, and it does not depend on the payload, the mask, the proposal, or whether the proposal was accepted (Section 3.2). By induction on t, the joint distribution of (H1:Ti+1,V1:Ti)(H_1:T_i+1,V_1:T_i), and in particular the transcript returned to A, is identical in 1 H_1 and 2 H_2. The argument holds conditionally on all earlier queries, so the view of A is identically distributed in the two experiments and ℙ[1=1]=ℙ[2=1]P[ H_1=1]=P[ H_2=1]. By the triangle inequality, Adv≤|ℙ[0=1]−ℙ[1=1]|+|ℙ[1=1]−ℙ[2=1]|=Adv,1.Adv steg_A≤ |P[ H_0=1]-P[ H_1=1] |+ |P[ H_1=1]-P[ H_2=1] |=Adv prf_ RangePRF,A_1. If RangePRF is a secure PRF, the right side is negligible in κ for every probabilistic polynomial-time A, so the construction is computationally covert. ∎ Undetectability is achieved by reducing to the security of RangePRF under Lemma 1. Below, we analyze the correctness and soundness. Let ℱt−1F_t-1 denote the complete state before step t, let Et=c^t≠ctE_t=1\ c_t≠ c_t\ indicate a substituted symbol, and let W=∑t=1NEtW= _t=1^NE_t. Corollary 1 (Substitution channel). The receiver observes exactly one symbol per token, so c^t c_t and ctc_t occupy the same position for every t, and c^t≠ct c_t≠ c_t if and only if the proposal at step t is rejected. Conditioned on ℱt−1F_t-1 and ata_t, Et∼Bernoulli((1−Kπt(at))+)E_t ((1-K _t(a_t))_+ ); if ata_t is uniform and independent of ℱt−1F_t-1, then ℙ[Et=1∣ℱt−1]=ΔK(pt)P[E_t=1 _t-1]= _K(p_t). Proof. Unmasking is a bijection of ℤKZ_K at every position, so c^t≠ct c_t≠ c_t if and only if a^t≠at a_t≠ a_t, which by Lemma 1(i) happens if and only if the proposal is rejected. Given ℱt−1F_t-1 and ata_t, the proposal is accepted with probability min1,Kπt(at) \1,K _t(a_t)\; averaging over a uniform ata_t gives 1K∑a(1−Kπt(a))+=∑a(1K−πt(a))+=ΔK(pt) 1K _a(1-K _t(a))_+= _a( 1K- _t(a))_+= _K(p_t), in agreement with Lemma 1(i). ∎ Theorem 2 (Correctness and soundness of the keyed strawman construction). (i) Correctness. With a τ-bounded-distance decoder DecECC, Extract returns m whenever W≤τW≤τ, so the scheme is δ-correct with δ≤ℙ[W>τ]δ [W>τ]. Given that the masks are uniform and ΔK(pt)≤Δ¯ _K(p_t)≤ for all t, then for every τ>NΔ¯τ>N , ℙ[W>τ]≤exp(−(τ−NΔ¯)22N).P[W>τ]≤ (- (τ-N )^22N ). (10) (i) Soundness. If Tag is a secure pseudorandom function, the scheme is sound for every decoder. Concretely, there is a probabilistic polynomial-time distinguisher 2A_2 against Tag such that Extract returns a message other than m or ⊥ with probability at most 2−λ+Adv,2(κ)2^-λ+Adv prf_ Tag,A_2(κ). Proof. (i) Correctness. We first show that decoding succeeds whenever at most τ symbols are substituted, and then bound the probability that more than τ are. By Corollary 1, c^t≠ct c_t≠ c_t exactly when Et=1E_t=1, so the received word c c differs from the codeword c=(u)c= ECC(u) in W positions. If W≤τW≤τ, the τ-bounded-distance decoder recovers (c^)=u=m|kv(,m) DecECC( c)=u=m\,\|\, Tag_k_v( sid,m) (Definition 1). The tag of m validates, so Extract returns m. Hence ℙ[≠m]≤ℙ[W>τ]P[ Extract≠ m] [W>τ]. It remains to bound ℙ[W>τ]P[W>τ]. The indicators EtE_t are not independent, because ptp_t depends on the earlier tokens, so we use a martingale bound in place of a Chernoff bound. Under uniform masks, Corollary 1 gives ℙ[Et=1∣ℱt−1]=ΔK(pt)≤Δ¯P[E_t=1 _t-1]= _K(p_t)≤ . Subtracting these conditional means, Ms=∑t≤s(Et−ΔK(pt)),s=0,…,N,M_s= _t≤ s (E_t- _K(p_t) ), s=0,…,N, is a martingale with respect to (ℱs)(F_s) whose increments lie in [−1,1][-1,1], and W=MN+∑t≤NΔK(pt)≤MN+NΔ¯W=M_N+ _t≤ N _K(p_t)≤ M_N+N . Therefore W>τW>τ implies MN>τ−NΔ¯M_N>τ-N , and the Azuma–Hoeffding inequality gives ℙ[W>τ]≤ℙ[MN>τ−NΔ¯]≤exp(−(τ−NΔ¯)22N).P[W>τ] [M_N>τ-N ]≤ (- (τ-N )^22N ). (i) Soundness. Let Bad be the event that Extract returns some m^∉m,⊥ m∉\m, \, which requires the decoded word to be m^|v m\,\|\, v with v^=kv(,m^) v= Tag_k_v( sid, m). Let 2A_2 be the probabilistic polynomial-time distinguisher that runs the protocol with its oracle in place of kv Tag_k_v and outputs 11 if Bad occurs. Replacing kv Tag_k_v by a uniformly random function R onto 0,1λ\0,1\^λ changes ℙ[]P[ Bad] by at most Adv,2Adv prf_ Tag,A_2, so it suffices to show ℙ[]≤2−λP[ Bad]≤ 2^-λ when R is used. In this case, verification compares v v with R(,m^)R( sid, m). R(,m^)R( sid, m) is uniform on 0,1λ\0,1\^λ and independent of v v, so the comparison succeeds with probability 2−λ2^-λ. ∎ Remarks. The error rate ΔK(pt) _K(p_t) is the imbalance of a random partition of the vocabulary under ptp_t, so it tracks the entropy of the position. When ptp_t spreads over many tokens, the buckets are nearly balanced and the symbol is reliable; when ptp_t concentrates on one token, all buckets but one are nearly empty, ΔK(pt) _K(p_t) approaches 1−1/K1-1/K, and the symbol is close to pure noise. 4.3 Limitations of Strawman The keyed strawman construction is provably undetectable, but its capacity is much lower than the cover text allows. Corollaries 1 and 2 point to two causes. 1. The receiver lacks a per-token distribution estimate. It runs no model, so it cannot compute the error rates ΔK(pt) _K(p_t) of Corollary 1 and must decode every position at the same error rate. This costs capacity. A decoder that knows each position’s error rate can approach the sum of the per-position capacities, whereas one that uses their average is limited to the capacity of the average channel, which is smaller because capacity is convex in the error rate; the gap is large when ΔK(pt) _K(p_t) is close to 00 or close to 1−1/K1-1/K and rarely in between. For K=2K=2, if half of the positions are noiseless and half are pure noise, a decoder that knows which half is which recovers 0.50.5 bits per token, while decoding at the average error rate 0.250.25 recovers at most 1−h(0.25)≈0.191-h(0.25)≈ 0.19, where h is the binary entropy function. 2. A fixed alphabet ignores the entropy of ptp_t. Every token carries log2K _2K bits although its entropy varies from token to token. A high-entropy token could hide up to H(pt)H(p_t) bits, its entropy, but is capped at log2K _2K. A low-entropy token cannot hide even log2K _2K bits, because by Corollary 1 its bucket imbalance ΔK(pt) _K(p_t) approaches 1−1/K1-1/K, so its symbol is close to pure noise. Such symbols carry no information themselves and, because the code treats all positions equally, raise the error rate that the whole codeword must be protected against, which lowers the rate for the informative positions as well. The alphabet should follow the entropy token by token, that is, K should adapt to the entropy of ptp_t. Both losses have the same cause. The two parties share no estimate of ptp_t, so neither can size the alphabet or tell a usable token from a noisy one. A realistic way to obtain such an estimate in the asymmetric setting is a small public draft model that both parties run on the public transcript alone; the sender’s private context, reasoning, and tool calls stay unshared, and the draft distribution becomes a proxy for ptp_t. The next section builds Codetta on this proxy. 5 Codetta Keyed Steganographic Protocol The strawman construction has unused capacity because the sender and receiver share no estimate of ptp_t. Codetta increases the capacity by introducing a public draft model that both the sender and the receiver can access to estimate the entropy of ptp_t. Both parties run the small public draft model on the public transcript and obtain qt=P(⋅∣Gt(V<t))q_t=P_ Draft(· G_t(V_<t)) as in Equation 2. The draft model sees only public information, which is visible to the sender, the receiver, and the auditor, and uses none of the sender’s internal state. Thus qtq_t serves as a proxy for ptp_t in entropy estimation. The Codetta keyed protocol keeps the structure of the strawman and changes two components. First, instead of using public hash functions to assign tokens to buckets, we utilize the draft model to minimize the bucket imbalance and thus the channel errors to improve capacity (Section 5.1). Second, the entropy estimate indicates the amount of information each token can carry, so the alphabet should follow the entropy of the text. Thus, we design an alphabet-adaptive ECC that replaces the block ECC, which is built for autoregressive generation. A conventional ECC must finish encoding before generation starts, but how much a token can carry is known only when generation reaches it. Thus, Codetta encodes online, committing one check per token as the entropy of that token is revealed, and the receiver decodes given the prefix (Section 5.2). The sampler is unchanged, so undetectability carries over from the strawman, and Section 5.3 shows how the draft model lowers the error rate of the hidden channel. Similar to the strawman construction, the two parties share a key sk=(km,kv)sk=(k_m,k_v); Section 6 removes this assumption. 5.1 Draft-Balanced Buckets At step t, both parties compute qtq_t and derive from it two public objects, the alphabet size KtK_t and a partition of V into KtK_t buckets (Algorithm 2, line 6). Both are deterministic functions of qtq_t and public parameters, so the sender and the receiver obtain the same objects without communicating. The draft model takes only the public transcript as input, which is visible to the sender, the receiver, and the auditor, so qtq_t reveals nothing about the sender’s internal state. Bucket balancing. Section 4 identified bucket imbalance as a major source of lost capacity, i.e., ΔK(pt) _K(p_t) can be large. To reduce ΔK(pt) _K(p_t), we design a function (qt,K) Bucket(q_t,K) that partitions V into K buckets of nearly equal mass under qtq_t. Since qtq_t serves as a proxy for ptp_t, the closer these two distributions are, the smaller ΔK(pt) _K(p_t) is. Specifically, (qt,K) Bucket(q_t,K) sorts the tokens under qtq_t in decreasing order and assigns each in turn to the bucket that is currently lightest. Ties are broken using a public rule. Since qtq_t requires only the public transcript, both parties can reproduce the buckets exactly. We use the notation f,t:→ℤKtf_ Bucket,t:V _K_t for the resulting map, Bt,aB_t,a for its buckets, πt(a)=pt(Bt,a) _t(a)=p_t(B_t,a) for the bucket masses under the sender’s base model, and write μt(a)=qt(Bt,a) _t(a)=q_t(B_t,a) for the masses under the public draft model. The imbalance of the partition under either distribution is measured as in Equation 4. Under the public draft model it is ΔK(qt)=12∑a|μt(a)−1K| _K(q_t)= 12 _a| _t(a)- 1K|, and under the sender’s base model it is ΔK(pt)=12∑a|πt(a)−1K| _K(p_t)= 12 _a| _t(a)- 1K|, which is known only to the sender. Alphabet selection. The second source of lost capacity in the strawman construction is that every token carries a symbol from the same alphabet ℤKZ_K, whatever its entropy (see Section 4.3). With the public draft model available to both parties, we design an alphabet size selection function (qt) ChooseAlphabet(q_t) that returns the estimated optimal number of buckets KtK_t for step t. A size Kt>1K_t>1 is admissible only if qtq_t has enough entropy to fill KtK_t buckets and the partition (qt,Kt) Bucket(q_t,K_t) is close to balanced under qtq_t: H(qt)≥log2Kt+γH,ΔKt(qt)≤θ,H(q_t)≥ _2K_t+ _H, _K_t(q_t)≤θ, (11) where HH is the Shannon entropy and γH,θ _H,θ are public thresholds. The entropy condition says that a symbol of log2Kt _2K_t bits should not exceed the token’s entropy under the draft model. However, this condition alone does not guarantee balance. A few tokens holding most of the mass of qtq_t still leave H(qt)H(q_t) large when the rest is spread over a long tail, but these heavy, indivisible tokens cannot be split evenly across KtK_t buckets, so even the best partition can be imbalanced. The second condition directly checks the partition’s imbalance under draft model. Among the admissible alphabet sizes, ChooseAlphabet returns the one with the highest score: log2Kt−h(e^Kt)−e^Ktlog2(Kt−1), _2K_t-h( e_K_t)- e_K_t _2(K_t-1), (12) the capacity of a KtK_t-ary symmetric channel with estimated error rate e^Kt e_K_t. The score is an information proxy for the capacity of alphabet size KtK_t, and the error rate e^Kt e_K_t is a pre-defined parameter calibrated on held-out data, per alphabet size. If no alphabet size is admissible, then Kt=1K_t=1 is selected, which means that the token carries no symbol, and the sender samples Yt∼ptY_t p_t directly (Algorithm 2, line 8). The thresholds, KmaxK_ , and the calibration tables e^Kt e_K_t are public parameters. Selecting KtK_t token by token raises an immediate question. An ECC that encodes the whole message before generation cannot produce a symbol whose alphabet is not determined until step t. We resolve this issue in Section 5.2, where the ECC fixes no codeword in advance but generates it on the fly, one symbol per step, in the alphabet selected for that step. Remarks. The sampler is the same as in the strawman, where the sender proposes from ptp_t inside the target bucket and corrects with maximal coupling. By Lemma 1, a symbol is substituted exactly when the proposal is rejected, which happens with probability ΔKt(pt) _K_t(p_t) on the partition of this step. By the triangle inequality, ΔKt(pt)≤12∑a|πt(a)−μt(a)|+12∑a|μt(a)−1Kt|≤TV(pt,qt)+ΔKt(qt), _K_t(p_t)≤ 12 _a | _t(a)- _t(a) |+ 12 _a | _t(a)- 1K_t | (p_t,q_t)+ _K_t(q_t), (13) since the bucket masses of two distributions differ by at most their total variation. The first term is the mismatch between the sender’s base model and the public draft model, which the ECC must absorb, and the second term is kept below θ by Equation 11. Here we use a small example to illustrate the effectiveness of bucket balancing. Suppose qtq_t puts masses 0.50.5, 0.30.3, and 0.20.2 on three tokens and Kt=2K_t=2. Balancing places the heaviest token alone in one bucket and the other two in the second, so both buckets have mass exactly 1/21/2 and Δ2(qt)=0 _2(q_t)=0. A random hash assigns the three tokens independently, producing bucket masses (1,0)(1,0), (0.8,0.2)(0.8,0.2), (0.7,0.3)(0.7,0.3), or (0.5,0.5)(0.5,0.5) with equal probability, and the expected imbalance is 0.250.25. If ptp_t is close to qtq_t, the sender’s rejection rate is close to 00 with balancing and 0.250.25 on average with the random hash function. At a low-entropy step, the gap is larger that under a random hash the imbalance approaches 1−1/K1-1/K regardless of the draft, whereas ChooseAlphabet gives such a step Kt=1K_t=1 so that it never enters the ECC. 5.2 Alphabet-Adaptive ECC From Section 5.1, the alphabet size changes from token to token. At every step, both parties compute KtK_t from public information only, including the published transcript and the draft model, and we call a step with Kt>1K_t>1 usable. The sampler of Section 5.1 expects one symbol in ℤKtZ_K_t at every usable step. The difficulty is that KtK_t is known only when generation reaches step t, by which time the symbols carrying the secret message of the previous t−1t-1 tokens are already embedded. A conventional ECC encodes the whole message into a codeword before transmission, so it cannot produce symbols in alphabets that are decided one step at a time. Running generation ahead to learn the sizes is not an option either, because the tokens that reveal KtK_t are the very tokens that carry the symbols, and once published they cannot be changed as rejecting and re-sampling a published token would alter the transcript distribution. A simple adaptation of a conventional ECC also falls short, because a binary ECC can pack a variable number of bits into each token only for alphabet sizes that are powers of two, so a step whose symbol alphabet has three, five, or seven possible values is rounded down to two or four, and the capacity in between is lost. We therefore design an alphabet-adaptive ECC that does not fix the codeword in advance. At each usable step it computes one symbol of the message in ℤKtZ_K_t, so every error stays a substitution of one symbol and the number of symbols grows with the number of usable tokens. Algorithm 2 presents the complete protocol. Algorithm 2 Codetta with draft-balanced buckets and an alphabet-adaptive ECC 1: secret key sk=(km,kv)sk=(k_m,k_v); session identifier sid; public horizon T; public draft model and view G; public ECC profile (degree law, support and coefficient rules); public checkpoints 2: 3: procedure Embed(sk,,msk, sid,m) 4: u←m|kv(,m)∈0,1Nu← m\,\|\, Tag_k_v( sid,m)∈\0,1\^N; s←0s← 0 5: for t=1,…,Tt=1,…,T do 6: qt←P(⋅∣Gt(V<t))q_t← P_ Draft(· G_t(V_<t)); Kt←(qt)K_t← ChooseAlphabet(q_t); Bt,⋅←(qt,Kt)B_t,·← Bucket(q_t,K_t) ⊳ public 7: pt←P(⋅∣Ht,V<t)p_t← P_ Base(· H_t,V_<t) ⊳ sender only 8: if Kt=1K_t=1 then sample Yt∼ptY_t p_t ⊳ the token carries no symbol 9: else 10: s←s+1s← s+1; derive (Ss,as,⋅)(S_s,a_s,·) from the ECC profile for modulus KtK_t 11: Cs←∑i∈Ssas,iuimodKtC_s← _i∈ S_sa_s,iu_i K_t; As←Cs+km(,s,Kt)modKtA_s← C_s+ RangePRF_k_m( sid,s,K_t) K_t ⊳ check, then mask 12: πt(a)←pt(Bt,a) _t(a)← p_t(B_t,a); sample Xt∼pt(⋅∣Bt,As)X_t p_t(· B_t,A_s) if πt(As)>0 _t(A_s)>0 ⊳ proposal from the target bucket 13: with probability min1,Ktπt(As) \1,K_t _t(A_s)\ set Yt←XtY_t← X_t; otherwise sample Yt∼ρtY_t _t ⊳ maximal coupling 14: end if 15: publish YtY_t; the cover process updates Ht+1H_t+1 16: end for 17: end procedure 18: 19: procedure Extract(sk,,V1:Tsk, sid,V_1:T) 20: s←0s← 0; factor graph ←∅G← ; m^←⊥ m← 21: for t=1,…,Tt=1,…,T do 22: recompute qtq_t, KtK_t, and Bt,⋅B_t,· as in Embed ⊳ public replay 23: if Kt>1K_t>1 then 24: s←s+1s← s+1; C^s←f,t(Yt)−km(,s,Kt)modKt C_s← f_ Bucket,t(Y_t)- RangePRF_k_m( sid,s,K_t) K_t ⊳ read bucket, unmask 25: append the check (Ss,as,⋅,Kt,C^s)(S_s,a_s,·,K_t, C_s) to G 26: end if 27: if t is a checkpoint then run BP on G; keep a candidate m^′ m whose tag validates as m m 28: end if 29: end for 30: return m m 31: end procedure Modular checks. Now we present the modular checks construction, which is at the heart of the alphabet-adaptive ECC that produces checks on the fly for the changing alphabet. A conventional ECC decides every symbol of the codeword before transmission, which is impossible when the alphabet changes at every token position. We take a different approach that instead of directly transmitting the message itself, the sender answers “questions” about the message, one “question” per usable token. The “questions” are public, so the receiver knows them as well. Each “question” is chosen at its own step, after KtK_t is computed by ChooseAlphabet, and it is designed to have exactly KtK_t possible answers, so the answer fits the alphabet of that usable token. For example, a token with Kt=3K_t=3 may carry the sum of two message bits modulo 33. The receiver collects the answers, a few of which can be wrong due to rejection in maximal coupling (see Section 4), and once it has enough such answers, it solves for the message similar to solving a system of equations with a few corrupted entries. There are several properties of such a construction to make it feasible for our setting. “Questions” can be posed for any number of answers, so the alphabet may change from token to token. “Questions” can be asked for as long as generation continues, so this construction becomes rateless. A wrong token introduces error only to its own answer, so the channel remains a substitution channel. Fountain codes [31, 46] follow the same principle over a fixed alphabet, with each transmitted symbol a random combination of message bits; the modular checks below extend it to alphabets that can vary from symbol to symbol. Concretely, as in the strawman construction of Section 4, the sender first protects the message with a validation tag, u=m|kv(,m)∈0,1Nu=m\,\|\, Tag_k_v( sid,m)∈\0,1\^N with N=n+λN=n+λ (line 4). The bits u1,…,uNu_1,…,u_N are the unknowns that the receiver aims to decode. Every usable step produces one check, indexed by s (line 10). Suppose that ChooseAlphabet returns Kt>1K_t>1 at step t. Each “question” is a modular check, which is a weighted sum of a few message bits reduced modulo KtK_t. A public ECC profile determines for check s a degree dsd_s, a support Ss⊆1,…,NS_s \1,…,N\ of size dsd_s, and coefficients as,i∈1,…,Kt−1a_s,i∈\1,…,K_t-1\ for i∈Ssi∈ S_s, and the sender computes the symbol (line 11) Cs=∑i∈Ssas,iuimodKt.C_s= _i∈ S_sa_s,i\,u_i K_t. (14) The profile determines degrees using a public distribution that includes checks of degree one and two, because such checks pin down single bits and let belief propagation start reliably. The degree distribution and the support and coefficient rules are public and fixed before the communication starts; they play a similar role to the parity-check matrix in an LDPC ECC. Masking and embedding. The check value is not uniform, so the sender masks it with a fresh pad in a similar way as in the strawman construction in Section 4: As=Cs+km(,s,Kt)modKt,A_s=C_s+ RangePRF_k_m( sid,s,K_t) K_t, (15) where the pad is a pseudorandom element of ℤKtZ_K_t. Because the alphabet size differs from check to check, RangePRF takes KtK_t as an input and returns a value uniform on ℤKtZ_K_t for that check. The masked symbol AsA_s is the target bucket of step t. The sender proposes Xt∼pt(⋅∣Bt,As)X_t p_t(· B_t,A_s), accepts it with probability min1,Ktπt(As) \1,K_t _t(A_s)\, and otherwise samples the residual ρt _t of Equation 6, exactly as in Algorithm 1 (lines 12 and 13). Compared with the strawman, only two inputs have changed. The buckets now are determined by the draft distribution, and the symbol comes from the modular check. Decoding. The receiver first replays the public computation (line 22). It runs the draft model on the transcript, recovers qtq_t, KtK_t, and the buckets at every step, and reads the answer A^s=f,t(Yt) A_s=f_ Bucket,t(Y_t) at every usable token. It then subtracts the pad of Equation 15 to obtain C^s C_s (line 24). Let tst_s be the step of check s and M the number of checks in the transcript. The receiver now holds a system of M equations in the N unknown bits, ∑i∈Ssas,iui≡C^s(modKts),s=1,…,M, _i∈ S_sa_s,i\,u_i≡ C_s K_t_s, s=1,…,M, (16) in which every equation whose proposal was rejected by maximal coupling has a wrong C^s C_s (line 25). Decoding therefore reduces to solving a sparse system of modular equations with a few corrupted entries, and belief propagation is a conventional tool for this problem, as it is for LDPC ECCs (Section 2.4). The receiver builds a factor graph with one variable node per bit and one factor per equation. The factor of equation s assigns to each local assignment uSsu_S_s the likelihood of the observed value under the calibrated error estimation, ϕs(uSs)=1−e^Ktsif ∑i∈Ssas,iui≡C^s(modKts),e^Kts/(Kts−1)otherwise, _s(u_S_s)= cases1- e_K_t_s&if _i∈ S_sa_s,iu_i≡ C_s K_t_s,\\[2.0pt] e_K_t_s/(K_t_s-1)&otherwise, cases (17) where e^K e_K is calibrated per alphabet size before the communication. See Appendix A for the details of belief propagation (BP). The receiver runs BP on the equations collected and obtains a candidate message m m (line 27). It accepts the candidate only if the tag validates, that is, if the decoded tag equals kv(,m^) Tag_k_v( sid, m). After the last token, it returns the accepted candidate, or ⊥ if none validated (line 30). Remarks. The undetectability, substitution channel, and correctness are proved in Section 5.3. The alphabet-adaptive ECC is rateless. Every additional usable token adds a check, and the receiver decodes as soon as the accumulated checks suffice, so neither party fixes a rate or a length in advance. The hidden channel has no insertions or deletions. Both parties derive KtK_t from the same public transcript and draft model, so they agree on usable tokens and on the index of every check. A rejected proposal changes the value of one check but not the alphabet. Finally, the alphabet is determined by the token’s entropy. A token with Kt=1K_t=1 does not contribute, and a token with a large KtK_t carries a symbol with log2Kt _2K_t bits, so the encoder places checks at usable positions and adapts each check to the selected alphabet. 5.3 Undetectability and Correctness of Codetta Keyed Protocol We analyze undetectability, the substitution channel, and correctness and soundness of Algorithm 2, following Section 4. All three rest on Lemma 1, the one-step lemma of the strawman, which applies unchanged. Part (i) of the lemma is the single-step form of undetectability, which Theorem 3 extends to whole transcripts and to pseudorandom masks, and parts (i) and (i) describe the errors that Corollary 2 and Theorem 4 count. The lemma fixes the complete state before step t, which includes the public prefix V<tV_<t and hence qtq_t, KtK_t, and the bucket splitting Bt,⋅B_t,·; its proof relies only on the partition being fixed and the symbol being uniform on ℤKtZ_K_t. It therefore holds at every usable step of Algorithm 2 with K=KtK=K_t. As in the strawman, Yt∼ptY_t p_t, the proposal is rejected with probability ΔKt(pt) _K_t(p_t), and the symbol is wrong exactly when the proposal is rejected. At a step with Kt=1K_t=1 the sender samples Yt∼ptY_t p_t directly, which is the lemma with a single bucket. Theorem 3 (Undetectability of Codetta). If RangePRF is a secure pseudorandom function, Codetta is computationally covert. Concretely, for every probabilistic polynomial-time distinguisher A in Definition 2 there is a probabilistic polynomial-time distinguisher 1A_1 against RangePRF such that Adv(κ)≤Adv,1(κ)Adv steg_A(κ) prf_ RangePRF,A_1(κ). Proof. We use a hybrid argument over three experiments. • 0 H_0: the experiment of Definition 2 with b=1b=1; every query is answered by Embed of Algorithm 2. • 1 H_1: identical to 0 H_0, except that every mask km(i,s,K) RangePRF_k_m( sid_i,s,K) is replaced by F(i,s,K)F( sid_i,s,K) for a uniformly random function F whose value at an input with alphabet size K is uniform on ℤKZ_K. • 2 H_2: the experiment with b=0b=0; every query is answered by ordinary sampling from the base model without an embedded message. Write ℙ[j=1]P[ H_j=1] for the probability that A outputs 11 in j H_j, so that Adv=|ℙ[0=1]−ℙ[2=1]|Adv steg_A=|P[ H_0=1]-P[ H_2=1]|. 0≈1 H_0≈ H_1. Let 1A_1 be the distinguisher against RangePRF that runs A, simulates the challenger with the base model, the draft model, and the alphabet-adaptive ECC, obtains every mask by querying its oracle at (i,s,Kt)( sid_i,s,K_t), and outputs whatever A outputs. When the oracle is km RangePRF_k_m, 1A_1 simulates 0 H_0 exactly; when it is a random function, 1A_1 simulates 1 H_1 exactly. Hence |ℙ[0=1]−ℙ[1=1]|=Adv,1|P[ H_0=1]-P[ H_1=1]|=Adv prf_ RangePRF,A_1, and 1A_1 runs A once plus one protocol execution per query, so it is probabilistic polynomial-time whenever A is. 1≡2 H_1≡ H_2. Fix a query (i,mi,Ti)( sid_i,m_i,T_i) and let ℱt−1F_t-1 be the complete state before step t, consisting of the sender’s state HtH_t, the transcript V<tV_<t, the message, and all earlier randomness. We compare the conditional distribution of (Yt,Ht+1)(Y_t,H_t+1) given ℱt−1F_t-1 in the two experiments. (a) The draft distribution qtq_t, the alphabet size KtK_t, and the partition Bt,⋅B_t,· are deterministic functions of V<tV_<t and public parameters (Algorithm 2, line 6), so they take the same values in both experiments and depend on the message only through the published prefix. (b) If Kt=1K_t=1, the sender samples Yt∼ptY_t p_t in 1 H_1 (line 8), which is the distribution of YtY_t in 2 H_2 by Equation 1. (c) If Kt>1K_t>1, the check index s is determined by V<tV_<t, and the pair (i,s)( sid_i,s) never repeats across queries and steps, so F(i,s,Kt)F( sid_i,s,K_t) is evaluated at a fresh point and is uniform on ℤKtZ_K_t, independent of ℱt−1F_t-1 and of CsC_s. Hence As=Cs+F(i,s,Kt)modKtA_s=C_s+F( sid_i,s,K_t) K_t is uniform given ℱt−1F_t-1, for every message, and Lemma 1(i) applied to the partition Bt,⋅B_t,· gives Yt|ℱt−1∼ptY_t _t-1 p_t in 1 H_1, which is again the distribution of YtY_t in 2 H_2. (d) After YtY_t is published, the sender’s state Ht+1H_t+1 is computed in the same way in both experiments; it is a function of HtH_t, V≤tV_≤ t, and fresh randomness of the agent, and it does not depend on the message, the mask, the token proposal, or whether the token proposal was accepted. By induction on t, the distribution of the transcript returned to A is identical in 1 H_1 and 2 H_2. So the view of A is identically distributed in the two experiments and ℙ[1=1]=ℙ[2=1]P[ H_1=1]=P[ H_2=1]. By the triangle inequality, Adv≤|ℙ[0=1]−ℙ[1=1]|+|ℙ[1=1]−ℙ[2=1]|=Adv,1.Adv steg_A≤ |P[ H_0=1]-P[ H_1=1] |+ |P[ H_1=1]-P[ H_2=1] |=Adv prf_ RangePRF,A_1. If RangePRF is a secure PRF, the right side is negligible in κ for every probabilistic polynomial-time A, so Codetta is computationally covert. ∎ Recall that check s is carried by token tst_s, and let M≤TM≤ T be the number of checks in the transcript. Let Es=C^s≠CsE_s=1\ C_s≠ C_s\ indicate a substituted check and W=∑s≤MEsW= _s≤ ME_s. Corollary 2 (Variable-alphabet substitution channel). The receiver observes exactly one check per usable token, and the usable steps and check indices are the same at both parties, so C^s C_s and CsC_s refer to the same check for every s. Moreover, C^s≠Cs C_s≠ C_s if and only if the proposal at step tst_s is rejected, and under uniform masks ℙ[Es=1∣ℱts−1]=ΔKts(pts)≤TV(pts,qts)+θ.P[E_s=1 _t_s-1]= _K_t_s(p_t_s) (p_t_s,q_t_s)+θ. Proof. KtK_t and f,tf_ Bucket,t are deterministic functions of V<tV_<t and public parameters, and both parties condition on the same published prefix whether or not a proposal was rejected, so they compute the same alphabet size at every step and advance s at the same steps. A rejection changes YtY_t and possibly C^s C_s, but KtK_t and s remain unchanged. Unmasking is a bijection of ℤKtZ_K_t, so C^s≠Cs C_s≠ C_s exactly when f,t(Yt)≠Asf_ Bucket,t(Y_t)≠ A_s, which by Lemma 1(i) happens exactly when the proposal token is rejected by maximal coupling; by Lemma 1(i) this has conditional probability ΔKt(pt) _K_t(p_t). The bound is Equation 13 with the constraint ΔKt(qt)≤θ _K_t(q_t)≤θ. ∎ Corollary 2 is the counterpart of Corollary 1. The channel is still a substitution channel, but its alphabet changes with the token, and its error rate is no longer the imbalance of a random partition. The public bucket partition imbalance is bounded by θ, and the remaining part is the mismatch between the sender’s base model and the public draft model. In the symmetric case of pt=qtp_t=q_t, the error rate is at most θ at every usable step. Theorem 4 (Correctness and soundness of Codetta). (i) Correctness. Suppose the masks are uniform and TV(pt,qt)≤εTV(p_t,q_t)≤ at every usable step, so that by Corollary 2 every check is substituted with conditional probability at most ε+θ +θ. For any decoder of the check sequence that recovers u whenever at most τ checks are substituted, the scheme is δ-correct with δ≤ℙ[W>τ]δ [W>τ], and for every τ>T(ε+θ)τ>T( +θ), ℙ[W>τ]≤exp(−(τ−T(ε+θ))22T).P[W>τ]≤ (- (τ-T( +θ))^22T ). (18) (i) Soundness. If Tag is a secure pseudorandom function, the scheme is sound for every decoder. Concretely, if the receiver validates at most Q candidate messages, there is a probabilistic polynomial-time distinguisher 2A_2 against Tag such that Extract returns a message other than m or ⊥ with probability at most Q 2−λ+Adv,2(κ)Q\,2^-λ+Adv prf_ Tag,A_2(κ). Proof. (i) Correctness. By Corollary 2, W counts the substituted checks, so a decoder that tolerates τ substitutions recovers u (m and its tag) whenever W≤τW≤τ. Hence, ℙ[≠m]≤ℙ[W>τ]P[ Extract≠ m] [W>τ]. For the tail bound we need a martingale with a fixed number of increments, but checks are emitted only at usable steps and their number M is random. We therefore index by steps instead of by checks. For a usable step t, let EtE_t be the indicator that its check is substituted and Δt=ΔKt(pt) _t= _K_t(p_t) the conditional probability of this event; for a step with Kt=1K_t=1, which emits no check, set Et=Δt=0E_t= _t=0. Then W=∑t≤TEtW= _t≤ TE_t, and by Corollary 2 ℙ[Et=1∣ℱt−1]=Δt≤ε+θP[E_t=1 _t-1]= _t≤ +θ at every step. Hence Zs=∑t≤s(Et−Δt)Z_s= _t≤ s(E_t- _t) is a martingale with increments in [−1,1][-1,1], and W=ZT+∑t≤TΔt≤ZT+T(ε+θ)W=Z_T+ _t≤ T _t≤ Z_T+T( +θ). Therefore W>τW>τ implies ZT>τ−T(ε+θ)Z_T>τ-T( +θ), and the Azuma–Hoeffding inequality gives Equation 18. (i) Soundness. Let Bad be the event that a wrong candidate passes validation, that is, some m^′≠m m ≠ m whose decoded tag equals kv(,m^′) Tag_k_v( sid, m ). Let 2A_2 be the probabilistic polynomial-time distinguisher that runs the protocol with its oracle in place of kv Tag_k_v and outputs 11 if Bad occurs. Replacing kv Tag_k_v by a uniformly random function R onto 0,1λ\0,1\^λ changes ℙ[]P[ Bad] by at most Adv,2Adv prf_ Tag,A_2, so it suffices to bound ℙ[]P[ Bad] when R is used. In this case, embedding evaluates R only at (,m)( sid,m), so the transcript, and hence every candidate produced from it, is independent of the values of R at all other points. Validating a candidate m^′≠m m ≠ m compares its decoded tag with R(,m^′)R( sid, m ), a fresh uniform value, so the comparison succeeds with probability 2−λ2^-λ. At most Q distinct candidates are validated, and a union bound gives ℙ[]≤Q 2−λP[ Bad]≤ Q\,2^-λ. ∎ Remarks. Theorem 4(i) covers bounded-distance decoders of the check sequence. Codetta decodes with belief propagation, which offers no such guarantee, and Section 7 reports its recovery rate on every workload instead. The tag separates the two possible outcomes of a decode. A failed decode returns ⊥ , and a wrong message passes validation only with the probability of Theorem 4(i). The tail bound also makes the difference from Theorem 2 visible. In the strawman, the compensator ∑tΔK(pt) _t _K(p_t) runs over every token, including the near-noise ones; in Codetta it runs over the usable tokens only, and every term is at most TV(pt,qt)+θTV(p_t,q_t)+θ. A usable token with alphabet size KtK_t carries one symbol out of KtK_t, so it conveys at most log2Kt _2K_t bits of payload under any ECC. The payload rate of a transcript therefore cannot exceed the average of log2Kt _2K_t over its tokens. The delivered rate falls short of this ceiling by the cost of substitution errors, check redundancy, and the tag. 6 Codetta Steganographic Key Exchange The protocols so far assume that the sender and the receiver share a key sk=(km,kv)sk=(k_m,k_v). Independently deployed agents have no such key, especially if they are hosted by different organizations. They cannot establish the keys in the open, because a public key or a ciphertext in a conversation is an obvious signal to the auditor that they are transmitting secrets. The key exchange itself must therefore be hidden in ordinary text without a key. Hiding without a key is much more challenging than keyed scenarios. In the keyed protocols, the mask is a pseudorandom pad that the auditor cannot compute without the key, while the sender and the receiver, who both hold the key, compute the same pad and cancel it. The pad is uniform to the auditor, and Lemma 1 preserves the original distribution for every message. This construction does not generalize to the keyless setting. One keyless way to make a token carry a symbol is a public hash. The sender draws candidate blocks of tokens from the base distribution and publishes one whose hash equals the symbol, and the receiver recomputes the hash of the published block to read the symbol. Every party can compute the hash, so every message is public. The transcript keeps the base distribution only if the symbols are uniform, because otherwise the published blocks will be biased. A recent work follows this route [49] and hides a key exchange whose messages are pseudorandom, so that every symbol is uniform by construction. The cost of this route lies in how the exchange is carried. The labels of a finite candidate pool are never perfectly balanced, and a sender that keeps the transcript distribution exact has to publish a block with the wrong label with probability equal to this imbalance, so a published symbol is wrong with a constant probability. The key exchange of [49] tolerates such noise at the level of key agreement, and the feedback compiler in its Section 8 transmits the exchange bit by bit through a signaling protocol. Each published message carries a single bit of a key-exchange message, and the sender publishes a fixed number of messages for every bit, chosen in advance so that the receiver reads the bit correctly with high probability. Section 7.4 estimates the cost of their construction on our workloads and compares it with Codetta. The same work also proves two impossibility results [49]. First, a pseudorandom code whose decoder is public cannot correct a constant fraction of bit flips; our carrier is not such a code, because the receiver decodes with its MLWE secret and no public decoding information exists. Second, a non-interactive key exchange with a pseudorandom transcript, in which the two messages are generated non-adaptively and every transcript bit is flipped independently with a constant probability, admits a quasi-polynomial attack. Our exchange satisfies neither condition. The sender’s response (w,z)(w,z) depends on the share b~ b that it has read, so the messages are adaptive, and the carrier only displaces each q-ary coefficient by a small amount, whereas the result assumes that every transcript bit is flipped with a constant probability. Codetta instead transports lattice coefficients directly through the carrier, without a separate bitwise signaling layer, and lets the MLWE absorb the carrier’s errors, and it certifies correctness on the workload itself (Theorem 7) instead of relying on the channel interface of their compiler, in which the sender knows the crossover probability of each channel use before sending and learns afterwards whether the bit was flipped. The messages of MLWE key exchange are pseudorandom vectors of coefficients in ℤqZ_q, and MLWE decryption tolerates small additive noise by design. We therefore send each coefficient as one q-ary symbol, about log2q≈11.7 _2q≈ 11.7 bits per carrier position, and we allow noise in the carrier channel (see Section 6.4 for concrete parameters). The two designs thus take different directions from the same exact-distribution-preserving sampling. The construction of [49] carries one bit per block and thereby works on short blocks of constant entropy, whereas Codetta carries a full q-ary symbol per position and therefore requires enough entropy in every block (Section 7.4 reports the failures on different workloads and models). A carrier error is a small displacement of a coefficient, which enters the exchange as extra noise and is absorbed together with the lattice noise, while a short ECC over the exchanged message corrects the residue. The carrier itself is exact. It publishes a block of text drawn from the base distribution at every position regardless of the symbol, so undetectability relies only on the pseudorandomness of the lattice messages. With the parameters of Section 6.4, a full exchange of a 128-bit key takes 1,280 carrier positions. In the following, Section 6.1 builds the carrier, Section 6.2 runs the exchange over it, Section 6.3 proves undetectability and correctness, and Section 6.4 instantiates the concrete parameters. 6.1 Lifted Exact-Cover Carrier The carrier builds on the keyless hash-based embedding of the previous paragraphs. Its unit is one carrier position, in which one party publishes one block of tokens and thereby transports one coefficient a∈ℤqa _q of a lattice message; both messages of the exchange are sequences of such coefficients. We call the party that publishes the block the sender and the party that reads it the receiver; both agents take both roles during the exchange. The naive embedding has two weaknesses. First, a block is published with a probability that depends on how many other blocks share its label, so for a fixed pool the published block is not a uniform member of the pool and is honest only after averaging over the hash values. Second, when the pool has no block with the target label, the fallback delivers a random value to the receiver, making the coefficient’s additive noise large. The carrier removes both weaknesses. Its selection rule makes the published block a uniform member of the pool for every fixed pool and label table, so the block is an honest sample regardless of the labels. When the pool has no block with the target label, the rule publishes a block whose label is close to the target, so an error is a small displacement of the target label. We first describe the candidate pool and the labels at one carrier position and then the selection rule. Algorithm 3 Lifted exact-cover carrier at one position 1: modulus q; public session identifier sid; public replica ratio β and pool size L=βqL=β q; public serializer g:ℤq→g:Z_q with reconstruction map g+:→ℤqg^+:Y _q (=ℤqY=Z_q and g=g+=g=g^+= id for the identity serializer); public hash Hash_Y with exact range Y 2: 3: procedure Publish(i,ai,a) 4: pi←p_i← the sender’s distribution over its next block ⊳ sender only 5: sample X0,…,XL−1∼piX_0,…,X_L-1 p_i independently ⊳ candidate pool, independent of a 6: yj←(,i,Xj)y_j← Hash_Y( sid,i,X_j) for j=0,…,L−1j=0,…,L-1 ⊳ public labels 7: sort the slots (a′,J)∈ℤq×0,…,β−1(a ,J) _q×\0,…,β-1\ by target label g(a′)g(a ) and the blocks by label yjy_j 8: ← Assign← the alignment of the two sorted lists under the cyclic rotation of least total squared displacement (modulo |||Y|) between g(a′)g(a ) and the label of the block at slot (a′,J)(a ,J) ⊳ bijection 9: sample J∼(0,…,β−1)J (\0,…,β-1\); publish X(a,J)X_ Assign(a,J) ⊳ uniform over the pool 10: end procedure 11: 12: procedure Read(i,Xi,X) 13: y←(,i,X)y← Hash_Y( sid,i,X) ⊳ recompute the label of the published block 14: return g+(y)∈ℤqg^+(y) _q ⊳ lift the label to a symbol 15: end procedure Consider carrier position i, and let pip_i be the sender’s honest distribution over its next response block given its own state and the transcript so far, where a block contains at most B tokens. We write (S)U(S) for the uniform distribution on a finite set S. The sender draws a pool of L=βqL=β q blocks X0,…,XL−1∼piindependently,X_0,…,X_L-1 p_i , where β≥1β≥ 1 is a public replica ratio (Algorithm 3, line 5). The pool is drawn by the sender’s model on its local context and does not depend on the target symbol a; the pool is revealed neither to the public nor to the receiver. Every block receives a public label yj=q(,i,Xj)∈ℤq,y_j= Hash_q( sid,i,X_j) _q, where q Hash_q is a hash with exact range ℤqZ_q whose input also includes a public session identifier sid, fresh for every exchange, and the position i, so that labels at different positions and in different exchanges are independent (line 6). Since the hash function is public, the receiver can compute the label of any published block (line 13). If the labels were perfectly balanced, every value of ℤqZ_q would appear exactly β times in the pool, and the sender could publish a block with label a chosen uniformly among its β copies. However, the labels of a random pool are not balanced, and publishing only blocks with the target label would bias the transcript toward the labels that are overrepresented in the pool. The sender instead fixes a bijection :ℤq×0,…,β−1⟶0,…,L−1 Assign:Z_q×\0,…,β-1\ \0,…,L-1\ between the L slots (a,J)(a,J) and the L blocks, samples a replica J∼(0,…,β−1)J (\0,…,β-1\), and publishes X(a,J)X_ Assign(a,J) (line 9). Because Assign is a bijection and (a,J)(a,J) is uniform when a is, the published index is uniform over the pool for every fixed pool, so the published block is an honest sample from pip_i with no constraint on the label. This selection rule follows the bundle sampler of [49], which also publishes a uniformly chosen member of a pool of honest candidates, so that the marginal distribution stays exactly honest and the imbalance of the labels becomes a decoding error. The carrier extends it from a binary label to a q-ary symbol and chooses the bijection so that an error becomes a small displacement of the symbol instead of a flipped bit. We call this construction a lifted exact cover. Every block is used by exactly one slot, which is the exact cover, and the replica index lifts the q labels to L=βqL=β q slots. Undetectability holds for every choice of the bijection, because the argument above used only the fact that Assign is a bijection. The choice of Assign only determines the carrier error, and we choose it to keep the error small. Specifically, the sender sorts the blocks by label and the slots by symbol (Algorithm 3, line 7). It then aligns the two sorted lists and rotates one list against the other. Each rotation is a bijection, and its cost is the total squared displacement between the label of each block and the symbol of its slot. The sender keeps the rotation of least cost and reads Assign off the resulting alignment (line 8). The costs of all L rotations can be computed together by a cyclic correlation in O(LlogL)O(L L) time. When the labels are nearly balanced, almost every slot receives a block with its own label. The remaining slots receive a block whose label differs from the symbol by a small amount. A carrier error is therefore a small displacement of a modulo q instead of a random value. For key exchange phases in which the receiver requires less precision, a public serializer g:ℤq→g:Z_q maps each symbol to a target label in a smaller alphabet Y, and a public reconstruction map g+:→ℤqg^+:Y _q lifts a received label back to a symbol. In such a phase, the blocks are hashed into Y instead of ℤqZ_q, the slot (a,J)(a,J) is matched to the target label g(a)g(a), and the receiver returns g+(y)g^+(y) for the label y it reads (Algorithm 3, line 14). The slots remain indexed by the uncompressed symbol a∈ℤqa _q, so the bijection and the published distribution are unchanged. 6.2 Key Exchange The exchange transports a random pre-key from one party to the other over the carrier of Section 6.1, and both parties derive the session key from the transmitted pre-key. We name the two parties by their roles in the keyed protocol that follows. The sender chooses the pre-key and later embeds messages under the resulting key, and the receiver recovers the pre-key and later extracts those messages. During the exchange, each party embeds the pseudorandom message into its own responses. The receiver publishes a pseudorandom share first, and the sender then publishes a vector and the masked pre-key, so the key exchange has three phases. Algorithm 4 shows the three phases with the sender on the left and the receiver on the right, and numbers the steps that the following paragraphs refer to. Algorithm 4 Three-phase key exchange over the lifted exact-cover carrier Public parameters. Session identifier sid, matrix A∈Rqk×kA∈ R_q^k× k, distributions χsec _sec and χerr _err, ECC (,)( ECC, DecECC) with codeword length N, serializers gb=g_b= id, gwg_w, gzg_z, and KDF. Every arrow sends one coefficient per carrier position through Algorithm 3, and V is the public transcript of the three phases. Sender Receiver Setup 1 sS∼χsecks_S _sec^k, e1∼χerrke_1 _err^k, e2∼χerre_2 _err sR∼χsecks_R _sec^k, eR∼χsecke_R _sec^k Phase 1, the receiver’s share 2 b←AsR+eR∈Rqkb← As_R+e_R∈ R_q^k 3 read b~∈Rqk b∈ R_q^k ←kd positions,gb [ 8.04996ptkd positions,\ g_b 8.04996pt] 8.04996ptb 8.04996pt Phases 2 and 3, the sender’s response 4 K0∼(0,1ℓ)K_0 (\0,1\ ); c+←(K0)| 0d−Nc^+← ECC(K_0)\,\|\,0^d-N 5 w←ATsS+e1∈Rqkw← A^Ts_S+e_1∈ R_q^k 6 z←b~TsS+e2+ι(c+)∈Rqz← b^\,Ts_S+e_2+ (c^+)∈ R_q 7 →kd positions,gw [ 8.04996ptkd positions,\ g_w 8.04996pt] 8.04996ptw 8.04996pt read w~∈Rqk w∈ R_q^k 8 →d positions,gz [ 8.04996ptd positions,\ g_z 8.04996pt] 8.04996ptz 8.04996pt read z~∈Rq z∈ R_q 9 ω←z~−sRTw~ω← z-s_R^T w 10 c^←(ω)[N] c← HD(ω)_[N]; K^0←(c^) K_0← DecECC( c) Key derivation and confirmation 11 KS←(K0,V)K_S← KDF(K_0,V) KR←(K^0,V)K_R← KDF( K_0,V) 12 embed a fixed message under KSK_S (Algorithm 2) →keyed protocol 8.04996ptkeyed protocol 8.04996pt validate under KRK_R, else restart The key exchange should fit the carrier of Section 6.1, which restricts the messages it transports in two ways. First, every transported symbol must be uniform on ℤqZ_q, since the published block is an honest sample only when the symbol is uniform (Lemma 2). Second, the exchange must tolerate a small error in every symbol, since the carrier can deliver a label near the target. A key transport based on MLWE satisfies both requirements by design. Under the MLWE assumption, every message of the transport is computationally indistinguishable from a uniform vector over ℤqZ_q, so each of its coefficients can be handed to the carrier as a uniform q-ary symbol. The transport is also robust to small additive errors, because the receiver recovers the payload by rounding each coefficient in the decoding to the nearer of two values that are q/2q/2 apart, and an error that is small compared with this distance does not change the rounding. A displacement introduced by the carrier therefore has the same effect as the lattice noise that the transport already tolerates, and the two can be analyzed together. We now describe the exchange step by step, following Algorithm 4. Setup. Let Rq=ℤq[x]/(xd+1)R_q=Z_q[x]/(x^d+1) be the polynomial ring of degree d, and let k be the module rank. An element of RqkR_q^k has kdkd coefficients in ℤqZ_q and occupies kdkd carrier positions. Let A∈Rqk×kA∈ R_q^k× k be a public random matrix, and let sid be a public session identifier that is fresh for every exchange and enters every hash of the carrier. Before the exchange starts, the receiver samples a secret sR∼χsecks_R _sec^k and an error eR∼χsecke_R _sec^k, and the sender samples a secret sS∼χsecks_S _sec^k and errors e1∼χerrke_1 _err^k and e2∼χerre_2 _err (step 4). Here χsec _sec and χerr _err are distributions over polynomials with small coefficients; see Section 6.4. The exchange sends three messages through the carrier, including the receiver’s share b∈Rqkb∈ R_q^k, the sender’s vector w∈Rqkw∈ R_q^k, and the masked pre-key z∈Rqz∈ R_q, which occupy kdkd, kdkd, and d carrier positions. A party reads each message with a small displacement, and we write the values it reads as b~∈Rqk b∈ R_q^k, w~∈Rqk w∈ R_q^k, and z~∈Rq z∈ R_q, and the displacements as ζb=b~−b _b= b-b, ζw=w~−w _w= w-w, and ζz=z~−z _z= z-z. The receiver’s share. In the first phase, the receiver computes b=AsR+eR∈Rqkb=As_R+e_R∈ R_q^k and publishes its kdkd coefficients, one per carrier position, with the identity serializer (step 4). The identity serializer is required in this phase, since the security proof needs the value that the sender reads to be uniform on RqkR_q^k (Lemma 3). The share is an MLWE sample under the receiver’s secret, so under the MLWE assumption it is computationally indistinguishable from uniform and can be handed to the carrier as a sequence of uniform symbols (Section 6.3). The sender reads b~=b+ζb b=b+ _b (step 4). The sender’s response. The sender samples a pre-key K0∼(0,1ℓ)K_0 (\0,1\ ) and encodes it with an ECC that corrects every error pattern of weight at most τ, c=(K0)∈0,1N,N≤d.c= ECC(K_0)∈\0,1\^N, N≤ d. It appends d−Nd-N zero bits to obtain c+∈0,1dc^+∈\0,1\^d and maps c+c^+ to the ring element ι(c+)∈Rq (c^+)∈ R_q, where ι places a 00 bit at coefficient 00 and a 11 bit at coefficient ⌊q/2⌉ q/2 (step 4). The sender then computes (steps 4 and 4) w w =ATsS+e1∈Rqk, =A^Ts_S+e_1∈ R_q^k, (19) z z =b~TsS+e2+ι(c+)∈Rq, = b^\,Ts_S+e_2+ (c^+)∈ R_q, (20) and publishes, in the second and third phases, the kdkd coefficients of w with serializer gwg_w and the d coefficients of z with serializer gzg_z (steps 4 and 4). The vector w is an MLWE sample under the sender’s secret and plays the same role for the sender as the share b plays for the receiver. The masked pre-key z hides the encoded pre-key ι(c+) (c^+) under the mask b~TsS+e2 b^\,Ts_S+e_2, which the sender computes from its own secret and the share it read. Lemma 3 proves that the coefficients of b, w, and z handed to the carrier are jointly pseudorandom, so the carrier transports them as uniform symbols. Receiver decoding. The receiver reads w~=w+ζw w=w+ _w and z~=z+ζz z=z+ _z through the reconstruction maps gw+g_w^+ and gz+g_z^+ (steps 4 and 4) and computes in step 4: ω=z~−sRTw~(modq).ω= z-s_R^T w q. The following expansion shows that the pre-key K0K_0 can be obtained from ω. z~ z equals: z~=b~TsS+e2+ι(c+)+ζz=sRTATsS+eRTsS+ζbTsS+e2+ζz+ι(c+), z= b^\,Ts_S+e_2+ (c^+)+ _z=s_R^TA^Ts_S+e_R^Ts_S+ _b^Ts_S+e_2+ _z+ (c^+), and the value that the receiver subtracts equals: sRTw~=sRTATsS+sRTe1+sRTζw.s_R^T w=s_R^TA^Ts_S+s_R^Te_1+s_R^T _w. Both contain the ring element sRTATsSs_R^TA^Ts_S, which combines the two secrets through the public matrix A, and this common term cancels in the subtraction, which leaves: ω=ι(c+)+eRTsS+ζbTsS+e2+ζz−sRTe1−sRTζw⏟noise(modq).ω= (c^+)+ e_R^Ts_S+ _b^Ts_S+e_2+ _z-s_R^Te_1-s_R^T _w_noise q. Every noise term is either a small error or displacement or the product of one with a small secret, so the noise is small compared with q/2q/2 in almost every coefficient. The receiver applies the hard-decision map :Rq→0,1d HD:R_q→\0,1\^d, which rounds each coefficient to the nearer of 00 and ⌊q/2⌉ q/2 , keeps the first N bits as c^=(ω)[N] c= HD(ω)_[N], and decodes K^0=(c^) K_0= DecECC( c) (step 4). A coefficient is decided wrongly only where the noise reaches about q/4q/4, and the ECC corrects up to τ such coefficients. Theorem 6 states this decoding condition exactly. Key derivation. In step 4, both parties derive the session key from the pre-key and the public transcript V of the exchange, KS=(K0,V)∈0,1κ,KR=(K^0,V)∈0,1κ,K_S= KDF(K_0,V)∈\0,1\^κ, K_R= KDF( K_0,V)∈\0,1\^κ, and the two keys agree whenever the receiver has decoded the pre-key K0K_0 correctly. Key confirmation. The two parties then run the keyed protocol of Section 5 under their keys to transmit a fixed public message (step 4). If the two keys agree, the receiver extracts the message and its tag validates. If they disagree, validation fails, and the parties repeat the exchange with fresh randomness. Each attempt fails independently with some probability p_ fail, so the probability that r independent attempts all fail is ≤pr≤ p_ fail^\,r. For example, an exchange that succeeds with probability 0.990.99 fails three attempts with a probability ≤10−6≤ 10^-6. 6.3 Undetectability and Correctness of Codetta Steganographic Key Exchange The auditor of this section is passive. It reads every public message and may query the carrier hash and the KDF, which we model as random oracles, but it cannot modify, delay, inject, or choose messages. Since the two parties never see the auditor’s queries, an auditor that queries the oracles during the exchange has the same view as one that makes the same queries after the transcript is complete, so we analyze the latter. Lemma 2 (Labeled lifted exact cover). Fix one position, candidate pool, label table, serializer, and bijection Assign. If (a,J)∼(ℤq×0,…,β−1)(a,J) (Z_q×\0,…,β-1\), then (a,J) Assign(a,J) is uniform over the L candidate indices, and after averaging over the pool the published block has exactly the distribution pip_i. If the symbols of all positions are independent and uniform, and independent of the pools, then the published blocks of all positions are jointly distributed as an honest transcript. For the identity serializer, the published block X and its label y are jointly distributed as X∼piX p_i and y∼(ℤq)y (Z_q) with X and y independent, so the value that the reader of the position obtains is uniform on ℤqZ_q. Proof. Fix the pool X0,…,XL−1X_0,…,X_L-1 and its label table, which fixes the bijection Assign. The pair (a,J)(a,J) is uniform over a set of size L, and Assign maps this set bijectively onto the L candidate indices. Hence the published index I=(a,J)I= Assign(a,J) is uniform over the indices. This holds for every pool and label table, so I is independent of the pool. Now let the pool vary. Its blocks are independent samples from pip_i, and I is uniform and independent of them, so the published block X=XIX=X_I has distribution pip_i. Duplicate blocks and unbalanced labels do not change this indices-level argument. The composition over positions follows from the chain rule. Condition on the public history before position i, which includes all earlier published blocks. Given this history, the pool at position i consists of independent samples from pip_i, and the symbol is uniform and independent of the pool by assumption. The argument above then shows that the published block at position i has distribution pip_i given the history. An honest transcript is generated by exactly these conditional distributions, so the joint distribution of all published blocks equals that of an honest transcript. For the identity serializer, the label of the published block is y=q(,i,X)y= Hash_q( sid,i,X). In the random oracle model, the value of the hash at the fresh input (,i,X)( sid,i,X) is uniform on ℤqZ_q for every fixed X, so y is uniform and independent of X. Note that y differs from the symbol a by the displacement of the carrier, and this displacement is correlated with a. The uniformity of y does not rely on the displacement, but only on y being the hash value at a uniformly selected block. Inputs at different positions and in different exchanges are distinct, so their labels are independent. With the identity serializer, the reader obtains y itself. ∎ Lemma 3 uses the last statement of the lemma for the first phase, in which the sender reads the share b~ b and uses it as a row of an MLWE matrix. For a lossy serializer, the label is uniform on the smaller alphabet Y, but the lifted value g+(y)g^+(y) is not uniform on ℤqZ_q, which is why the first phase uses the identity serializer. Uniformity in the lemma is over the randomness of the random oracle, and a label that is predictable because its block is likely under pip_i is compatible with the argument, since the MLWE assumption hands the matrix M to the distinguisher anyway. Let Advk,ℬ(κ)Adv mlwe_k,B(κ) be the advantage of a distinguisher ℬB in telling (A,AsR+eR)(A,As_R+e_R) from (A,U)(A,U) for A∼(Rqk×k)A (R_q^k× k) and U∼(Rqk)U (R_q^k), and let Advk+1,ℬ(κ)Adv mlwe_k+1,B(κ) be its advantage in telling (M,MsS+e)(M,Ms_S+e) from (M,U′)(M,U ) for M∼(Rq(k+1)×k)M (R_q^(k+1)× k), e=(e1,e2)e=(e_1,e_2), and U′∼(Rqk+1)U (R_q^k+1). These are the two decisional MLWE assumptions behind the receiver’s share and the sender’s response. For a passive auditor A, let Adv(κ)Adv cover_A(κ) be its advantage in distinguishing the public transcript from an honest transcript, and Adv(κ)Adv key_A(κ) its advantage in additionally distinguishing the sender’s key from an independent uniform κ-bit string. For a distribution D over complete sessions, let δ=ℙΩ∼[KR≠KS] _D=P_ [K_R≠ K_S] be the probability that the two parties end with different keys. Lemma 3 (Joint pseudorandomness of the transported symbols). Consider the experiment in which a passive auditor reads the completed transcript of the exchange, and the modified experiment in which the carrier is fed independent uniform symbols at every position of all three phases instead of the coefficients of b, w, and z. For every probabilistic polynomial-time auditor A there are probabilistic polynomial-time distinguishers ℬ1B_1 and ℬ2B_2 such that A distinguishes the two experiments with advantage at most Advk,ℬ1(κ)+Advk+1,ℬ2(κ)Adv mlwe_k,B_1(κ)+Adv mlwe_k+1,B_2(κ). Proof. We use a hybrid argument over three experiments, where the auditor reads the completed transcript. • 0 H_0: the real exchange of Algorithm 4. • 1 H_1: identical to 0 H_0, except that the receiver feeds the carrier a uniform vector ub∼(Rqk)u_b (R_q^k) in place of b=AsR+eRb=As_R+e_R; the sender is unchanged and computes w and z from the labels b~ b it reads. • 2 H_2: identical to 1 H_1, except that the sender feeds the carrier a uniform pair (uw,uz)∼(Rqk×Rq)(u_w,u_z) (R_q^k× R_q) in place of (w,z)(w,z); this is the modified experiment of the lemma. Write ℙ[j=1]P[ H_j=1] for the probability that A outputs 11 in j H_j. 0≈1 H_0≈ H_1. Let ℬ1B_1 be the distinguisher that receives (A,t)(A,t) with t∈Rqkt∈ R_q^k, runs the exchange with A as the public matrix and the coefficients of t as the receiver’s symbols, simulates the sender honestly, runs A on the resulting transcript, and outputs the output of A. When t=AsR+eRt=As_R+e_R, ℬ1B_1 simulates 0 H_0 exactly; when t is uniform, it simulates 1 H_1 exactly. Hence |ℙ[0=1]−ℙ[1=1]|=Advk,ℬ1. |P[ H_0=1]-P[ H_1=1] |=Adv mlwe_k,B_1. 1≈2 H_1≈ H_2. In 1 H_1, the symbols of the first phase are uniform, so by Lemma 2 the published blocks of the first phase are honest samples and the vector b~ b of their labels is uniform on RqkR_q^k and independent of the blocks and of A. Here b~ b is the vector of hash values q(,i,Xi) Hash_q( sid,i,X_i) of the published blocks, and its uniformity comes from the hash; the carrier displacement b~−ub b-u_b is correlated with ubu_b, but ubu_b enters 1 H_1 only through the selection of the blocks. Let M=(ATb~T)∈Rq(k+1)×k,e=(e1,e2)∈Rqk+1,M= pmatrixA^T\\ b^\,T pmatrix∈ R_q^(k+1)× k, e=(e_1,e_2)∈ R_q^k+1, so that M is uniform and the sender’s symbols in 1 H_1 are (w,z)=MsS+e+(0,ι(c+)).(w,z)=Ms_S+e+(0, (c^+)). In 2 H_2 the sender’s symbols are (uw,uz)(u_w,u_z), and (uw,uz)−(0,ι(c+))(u_w,u_z)-(0, (c^+)) is again uniform, so the two experiments differ exactly in whether MsS+eMs_S+e or a uniform element of Rqk+1R_q^k+1 is added to (0,ι(c+))(0, (c^+)). Let ℬ2B_2 be the distinguisher that receives (M,t′)(M,t ) with t′∈Rqk+1t ∈ R_q^k+1 and proceeds as follows. (a) It uses the first k rows of M as ATA^T and reads the last row as b~∈Rqk b∈ R_q^k. (b) For each position i of the first phase, it samples the pool honestly, publishes a uniformly chosen pool member XiX_i, and computes q(,i,Xi) Hash_q( sid,i,X_i) as the coefficient of b~ b that position i carries. By Lemma 2, the published block and its label have exactly their joint distribution in 1 H_1, and no earlier oracle query constrains the computed hash value. (c) It runs the second and third phases of the carrier with the symbols t′+(0,ι(c+))t +(0, (c^+)), runs A on the completed transcript, and outputs the output of A. When t′=MsS+et =Ms_S+e, ℬ2B_2 simulates 1 H_1 exactly; when t′t is uniform, it simulates 2 H_2 exactly. Hence |ℙ[1=1]−ℙ[2=1]|=Advk+1,ℬ2. |P[ H_1=1]-P[ H_2=1] |=Adv mlwe_k+1,B_2. By the triangle inequality, |ℙ[0=1]−ℙ[2=1]|≤Advk,ℬ1+Advk+1,ℬ2, |P[ H_0=1]-P[ H_2=1] | mlwe_k,B_1+Adv mlwe_k+1,B_2, and both distinguishers run A once plus one execution of the exchange, so they are probabilistic polynomial-time whenever A is. ∎ Theorem 5 (Undetectability and key security). For every probabilistic polynomial-time passive auditor A making at most Q_ KDF KDF queries, there are probabilistic polynomial-time distinguishers ℬ1B_1 and ℬ2B_2 such that Adv(κ) cover_A(κ) ≤Advk,ℬ1(κ)+Advk+1,ℬ2(κ), mlwe_k,B_1(κ)+Adv mlwe_k+1,B_2(κ), (21) Adv(κ) key_A(κ) ≤Advk,ℬ1(κ)+Advk+1,ℬ2(κ)+Q2ℓ. mlwe_k,B_1(κ)+Adv mlwe_k+1,B_2(κ)+ Q_ KDF2 . (22) Proof. By Lemma 3, the auditor’s view is indistinguishable, up to Advk,ℬ1+Advk+1,ℬ2Adv mlwe_k,B_1+Adv mlwe_k+1,B_2, from the transcript of an exchange whose carrier is fed independent uniform symbols at every position. By Lemma 2, composed over positions and applied with slots indexed by ℤqZ_q regardless of the serializers, that transcript consists of honest samples, which proves Equation 21. In the modified experiment, the transcript is independent of the pre-key K0K_0, so the sender’s key (K0,V) KDF(K_0,V) is uniform unless the auditor queries the KDF at the point (K0,V)(K_0,V), which happens with probability at most Q/2ℓQ_ KDF/2 , and this proves Equation 22. ∎ Correctness relies on a deterministic decoding region. The next theorem does not assume any model of the carrier errors and a concrete workload determines how often an execution leaves the region. Theorem 6 (Noise-resilient decoding). For any realized execution, write b~=b+ζb b=b+ _b, w~=w+ζw w=w+ _w, and z~=z+ζz z=z+ _z modulo q, where ζw _w and ζz _z include both the serializer reconstruction error and the carrier displacement. The receiver’s residual satisfies ω=ι(c+)+eRTsS+ζbTsS+e2−sRTe1−sRTζw+ζz(modq).ω= (c^+)+e_R^Ts_S+ _b^Ts_S+e_2-s_R^Te_1-s_R^T _w+ _z q. (23) Let c^=(ω)[N] c= HD(ω)_[N] and W=dH(c^,c)W=d_H( c,c). If W≤τW≤τ, then the decoder recovers K0K_0 and KR=KSK_R=K_S, for arbitrary values of (ζb,ζw,ζz)( _b, _w, _z). Proof. Substitute b=AsR+eRb=As_R+e_R, w=ATsS+e1w=A^Ts_S+e_1, and z=b~TsS+e2+ι(c+)z= b^\,Ts_S+e_2+ (c^+) into ω=z~−sRTw~ω= z-s_R^T w. The two copies of sRTATsSs_R^TA^Ts_S cancel, which yields Equation 23. The ECC corrects every error pattern of weight at most τ, so the recovered pre-key and the transcript agree at both parties, and so do their KDF outputs. ∎ Equation 23 separates the noise of the lattice scheme from the noise of the carrier. The lattice noise terms eRTsSe_R^Ts_S, e2e_2, and sRTe1s_R^Te_1 are in the MLWE schemes, and the carrier adds ζbTsS _b^Ts_S, sRTζws_R^T _w, and ζz _z. Because sRs_R and sSs_S are small, a displacement of a few units in a coefficient of b or w adds only a few units to the residual, and a displacement of z enters directly. The hard decision is wrong only in the coefficients where these terms accumulate to about q/4q/4, and the ECC corrects up to τ such coefficients. Corollary 3 (Workload-specific correctness). For every distribution D over the complete sessions, δ≤ℙΩ∼[W>τ] _D _ [W>τ]. Since the displacement depends on the language model and the task, we certify correctness empirically. Theorem 7 (Empirical certification). Let Ω1,…,Ωm∼ _1,…, _m be independent complete sessions, let WiW_i be the value of W in session Ωi _i, let Fi=Wi>τF_i=1\W_i>τ\, and let S=∑i=1mFiS= _i=1^mF_i. For a confidence level 1−α1-α and S<mS<m, with probability at least 1−α1-α over the evaluation sample, δ≤ℙ[W>τ]≤Beta−1(1−α;S+1,m−S), _D _D[W>τ] ^-1(1-α;\,S+1,\,m-S), and for S=0S=0 the bound is δ≤1−α1/m _D≤ 1-α^1/m. Proof. The FiF_i are independent Bernoulli variables with mean ℙ[W>τ]P_D[W>τ], the bound is the exact one-sided Clopper–Pearson bound for their mean, and Corollary 3 transfers it to key disagreement. ∎ 6.4 Instantiation The proofs above hold for any choice of the lattice parameters, the serializers, and the ECC. This section fixes the choice used in the evaluation and states the security level it provides. The engineering parameters of the carrier, such as the replica ratios and the block length, do not enter the proofs, and Section 7 gives them with the experimental setup. Lattice parameters. We use the ring RqR_q with d=256d=256 and q=3329q=3329, rank k=2k=2, χsec=3 _sec= CBD_3, and χerr=2 _err= CBD_2, where η CBD_η is the centered binomial distribution of parameter η. These are the parameters of ML-KEM-512 [36]. The two assumptions of Theorem 5, decisional MLWE with k samples for the share and with k+1k+1 samples for the response, are the two assumptions in the IND-CPA security proof of ML-KEM-512, at the same ring, modulus, rank, and noise distributions [36]. The exchange therefore relies on the same MLWE problems as ML-KEM-512, which NIST places in security category 1, at least as hard to break as exhaustive key search on AES-128. Serializers. The share b is sent with the identity serializer, as Lemma 3 requires. The response uses gw=Compress10g_w=Compress_10 and gz=Compress4g_z=Compress_4, the ciphertext compression of ML-KEM-512, and the hard-decision map HD is Compress1Compress_1. Compression to 1010 bits changes a coefficient by at most q/211≈1.6q/2^11≈ 1.6 and compression to 44 bits by at most q/25≈104q/2^5≈ 104, and both are well below the decision threshold of q/4≈832q/4≈ 832 in Equation 23. Pre-key and ECC. The pre-key has ℓ=128 =128 bits, which matches the security category and makes the term Q/2ℓQ_ KDF/2 in Equation 22 negligible at the same level, and the session key has κ=256κ=256 bits. The ECC must place its codeword in the d=256d=256 coefficients of one ring element and carry at least ℓ information bits, and within these two constraints we take the largest correction radius. The binary BCH code of length 255255 and dimension 131131 of Section 2.4 corrects τ=18τ=18 errors and meets both constraints. Its 131 information bits are the pre-key followed by three zero bits, and the unused coefficient of the ring element is set to zero. If the hard decisions were wrong independently with probability p per coefficient, this code would fail with probability at most 10−610^-6 for every p≤0.0196p≤ 0.0196. Section 7 reports the measured failure rates. The exchange occupies kd+kd+d=1,280kd+kd+d=1,280 carrier positions. 7 Evaluation 7.1 Experimental setup Tasks. We evaluate on three simulated agent workloads. Financial is a synthetic issuer-intelligence task with 20 issuers and 100 database records: the receiver agent asks about an issuer’s financial information, and the sender agent answers from its internal database. IFEval [61] consists of natural-language requests with constraints on length, structure, wording, and formatting. CTF uses the offline InterCode-CTF [56] adaptation of picoCTF [8]. For each CTF challenge, an agent first solves the challenge with shell and Python tools in a sandbox, and the carrier is the technical solution report that the same model then writes from its complete solve trajectory. These tasks simulate the realistic scenarios we have introduced in Section 1. In Financial and IFEval, the agents communicate in a conversational setup, and in CTF, the agents communicate by reading and writing to a shared file system. Asymmetry. The sender agent runs a large base model on its full private context; the receiver sees only public transcript, including its own request, the sender’s response, and public problem statement. On Financial, the private context is the retrieved records. On IFEval, the sender first drafts a plan in its thinking trace, and that trace is the private context. On CTF, the private context is the agent’s full problem solving trajectory, including the task files, the tool commands, and the tool outputs. The receiver does not access the sender’s model, internal state, or private context. A draft-assisted receiver runs a small public draft model on the visible context alone; a model-free receiver does not run a language model. Models. For sender models, we evaluate on widely used open-sourced models, including Qwen2.5-7B [55], Llama-3.1-8B [18], and Ministral-3-8B [30]; the public draft models are Qwen2.5-1.5B, Llama-3.2-1B, and Ministral-3-3B. The model-mismatch ablation below pairs them across families, and the draft-size ablation additionally uses Qwen2.5-0.5B, 3B, and 7B as drafts. Baselines & Settings. ARS [4] is the state-of-the-art practical steganographic protocol under asymmetric resources, and we use its official implementation. We also construct a second baseline, HARQ LDPC, which replaces our alphabet-adaptive ECC with a rateless LDPC code: a 5G NR mother code of rate 0.20.2 whose parity bits are sent incrementally until the receiver decodes. We evaluate it in a draft-assisted and a draft-free configuration, using the optimized implementation in NVIDIA Sionna [23]. Codetta and the LDPC baselines carry 1,024 payload bits per message and append a 32-bit tag, so each message is 1,056 bits. The official ARS implementation delivers far fewer bits per token, so we give it a 128-bit payload on Financial and IFEval and a 16-bit payload on CTF; a shorter payload only helps ARS in a capacity comparison. We evaluate the average capacity of 25 independent secret messages with the same payload seed. A secret message spans several responses, i.e., the sender keeps embedding it across consecutive responses until the receiver decodes it, and when a workload runs out of requests we rotate through its request pool again. Our primary metric is the end-to-end delivered payload rate (capacity) Rpayload=correctly recovered payload bitseffective visible carrier tokens.R_payload= correctly recovered payload bitseffective visible carrier tokens. We also report encoding and decoding speed in tokens per second. We run the experiments on one NVIDIA H200 GPU. Ablations. To better understand the effectiveness of different components, we conduct three ablation studies. First, we vary information asymmetry by revealing 0%0\%, 25%25\%, 50%50\%, 75%75\%, or 100%100\% of the private context to the receiver. Second, we vary model mismatch across same-model, cross-size, and cross-family sender–draft pairs. Third, we remove one component of our code at a time by comparing with LDPC baselines: dropping the draft model removes public channel estimation, and fixing the alphabet size removes adaptive alphabet size selection, so the two variants separate the capacity gained from each. Key exchange. We run the key exchange of Section 6 with the three sender models on Financial, IFEval, and CTF. Each of the m=100,000m=100,000 sessions replays the exchange algebraically, with fresh lattice randomness and with displacements drawn independently for every position from the distribution measured on the sender model’s candidate pools under eight independent session identifiers, so Theorem 7 certifies the failure probability under this measured displacement distribution. The carrier uses the first complete response block of a turn as its token block, capped at B=64B=64 tokens, and the replica ratios are (βb,βw,βz)=(4,4,1)( _b, _w, _z)=(4,4,1). The Compress4Compress_4 phase has only 16 labels, so one replica suffices there. 7.2 Capacity of keyed protocols Table 1 reports the payload rate of the three methods on the three workloads and the three model pairs. Every cell recovered all 25 messages. Codetta delivers between 4.1 and 6.4 times the rate of the draft-free LDPC baseline and between 16 and 94 times the rate of ARS. The gain over the draft-free baseline is consistent across models and workloads, and Section 7.3 separates the two components behind it. The absolute rates differ by an order of magnitude across settings because they follow the entropy of the carrier text. Ministral writes the most varied text and reaches 0.45 to 0.57 bits per token on Financial and IFEval. Qwen on CTF is the other extreme. Its reports copy long spans of the private solve trajectory verbatim, 60% of the body tokens have an entropy below 0.1 bits, and every method drops below 0.04 bits per token there. Financial IFEval CTF Method Qwen Llama Ministral Qwen Llama Ministral Qwen Llama Ministral Capacity (bits per token) Codetta 0.1354 0.2289 0.4476 0.2510 0.3544 0.5685 0.0303 0.2844 0.2511 HARQ LDPC, draft-free 0.0280 0.0358 0.0936 0.0528 0.0665 0.1378 0.0072 0.0465 0.0571 ARS 0.0016 0.0142 0.0131 0.0044 0.0189 0.0204 0.0003 0.0064 0.0064 Gain of Codetta over HARQ LDPC 4.8× 6.4× 4.8× 4.7× 5.3× 4.1× 4.2× 6.1× 4.4× over ARS 87× 16× 34× 57× 19× 28× 94× 44× 39× Encoding throughput (tokens per second) Codetta 244 204 155 212 350 152 72 85 56 HARQ LDPC, draft-free 306 249 203 331 472 205 84 90 63 ARS 248 207 172 258 340 172 84 91 63 Decoding throughput (tokens per second) Codetta 1.0k 1.3k 0.7k 0.5k 1.0k 0.8k 0.2k 0.4k 0.2k HARQ LDPC, draft-free 381k 393k 391k 251k 341k 363k 16k 14k 17k ARS 7.5k 8.0k 8.0k 7.5k 8.0k 8.0k 42k 38k 41k Table 1: Capacity in bits per token, the gain of Codetta over each baseline, and throughput. Each experiment embeds 25 independent messages with the Qwen2.5-7B, Llama-3.1-8B, or Ministral-3-8B sender; Codetta uses the matching Qwen2.5-1.5B, Llama-3.2-1B, or Ministral-3-3B draft. Codetta and LDPC carry 1,024 bits per message, ARS carries 128 bits (16 on CTF). All of the messages are successfully recovered (25×102425× 1024 bits for every experiment on Codetta). Throughput is measured in output tokens per second with batch size 10 on one NVIDIA H200 GPU. Task quality. Theorem 3 guarantees that the covert transcripts follow the sender’s own distribution, so we do not measure their perplexity and instead check the task quality directly on IFEval, whose scorer is automatic. Ordinary responses of Qwen, Llama, and Ministral reach a strict instruction-following accuracy of 0.795, 0.795, and 0.744 on the evaluation prompts, and the covert transcripts of Codetta reach 0.718, 0.795, and 0.615. No method differs significantly from ordinary generation under a two-sided exact McNemar test over the 25 messages, with a smallest p-value of 0.1250.125. Speed. Embedding adds a draft forward pass and the coupling step to every token, and the throughput rows of Table 1 present this cost. The Codetta sender runs at 82% to 103% of the speed of the ARS sender across the different models and tasks, and at 88% or higher in all but one, because generation time is dominated by the base model and the draft is much smaller. The draft-free LDPC sender is the fastest, since it samples from the base model with no draft at all. For decoding cost, the two baselines decode with hashes alone and reach thousands to hundreds of thousands of tokens per second, while the Codetta receiver replays the draft model over the transcript and decodes at 240 to 1,260 tokens per second, still 2 to 6 times faster than the sender generates. 7.3 Ablations of Codetta keyed protocol All ablations use the Financial workload and the Qwen2.5-7B sender. Shared context. Figure 1 varies the fraction of the sender’s private records that the receiver also sees, from the primary asymmetric setting, in which the receiver sees none of them, to identical prompts, in which the receiver sees the whole record of 1,605 tokens on average. We plot two drafts, the 1.5B draft of the main experiments and a 7B draft that is the same model as the sender. Capacity grows monotonically with the shared context for both drafts: the 1.5B draft rises from 0.135 to 0.170 bits per token, and the 7B draft rises from 0.132 to 0.231 bits per token. The gain comes from a draft that tracks the sender’s distribution more closely, so that fewer proposals are rejected: the symbol error rate falls from 52% to 37% with the 1.5B draft and from 43% to 17% with the 7B draft. At full sharing with the 7B draft, the draft and base distributions coincide at every position, and the remaining 17% comes from the bucket discretization alone. The figure also shows the value of a stronger draft. Without shared context, the two drafts deliver the same capacity up to noise, since the 7B draft still has to guess the private records. Once the receiver shares part of the context, the stronger draft delivers more, by 18% at half sharing and by 36% at full sharing. Accordingly, a stronger draft model yields a higher capacity and its advantage grows with the shared portion of the sender’s context. Figure 1: Capacity on Financial with the Qwen2.5-7B sender as the receiver sees a growing prefix of the sender’s private records, for a 1.5B and a 7B draft. The upper axis gives the shared fraction. Each point embeds 25 messages of 1,024 bits. Model mismatch. Table 2 pairs each sender with drafts from all three families. Cross-family pairs use a public byte-level bridge between the two tokenizers. In these experiments, the delivered payload rate varies more across sender models than across draft models. Ministral keeps 0.32 to 0.45 bits per token with every draft, and Qwen stays between 0.12 and 0.14. A same-family draft is best for each sender, and a cross-family draft loses 8% to 29% against it. Draft Sender Qwen2.5-1.5B Llama-3.2-1B Ministral-3-3B Qwen2.5-7B 0.1354 0.1187 0.1250 Llama-3.1-8B 0.2047 0.2289 0.1847 Ministral-3-8B 0.3187 0.3252 0.4476 Table 2: Capacity of Codetta on Financial workload in bits per token for different pairs of sender and draft. All of the experiments recovered all 25 messages. Components. Table 3 removes one component of Codetta at a time on Financial. The last row is the draft-free LDPC code, and each row above it adds one component. The draft model offers the receiver balanced buckets, while the alphabet size stays fixed at two. It raises the capacity from 0.0280 to 0.0494 bits per token on Qwen (+76%), from 0.0358 to 0.0574 on Llama (+60%), and from 0.0936 to 0.1342 on Ministral (+43%). Adaptive alphabet size selection, still restricted to powers of two by the LDPC code, raises the capacity further to 0.0885 (+79%), 0.1718 (+199%), and 0.3634 (+171%) bits per token. And finally, the alphabet-adaptive ECC replaces the LDPC code, supports every alphabet size, and generates its checks online, which raises the capacity to 0.1354 (+53%), 0.2289 (+33%), and 0.4476 (+23%) bits per token. Accordingly, every component contributes for every sender, and the three components together deliver 4.8 to 6.4 times the capacity of the draft-free code, as reported in Table 1. Method Qwen Llama Ministral Codetta 0.1354 0.2289 0.4476 HARQ LDPC with draft, power-of-two K 0.0885 0.1718 0.3634 HARQ LDPC with draft, fixed K=2K=2 0.0494 0.0574 0.1342 HARQ LDPC, draft-free 0.0280 0.0358 0.0936 Table 3: Component ablation on Financial in bits per token. From top to bottom, each row removes one component: the alphabet-adaptive ECC, then the adaptive alphabet size, then the public draft model. 7.4 Key exchange Table 4 summarizes the correctness of the key exchange and the number of visible tokens it publishes, for the three senders on the three workloads. No session failed on Financial for any sender, and 12, 8, and 0 of the 100,000100,000 sessions failed on IFEval for Qwen, Llama, and Ministral. On CTF, 379 sessions failed for Qwen, and none failed for Llama and Ministral. Theorem 7 turns these counts into one-sided 95%95\% bounds on the failure probability δ _D: 3.0×10−53.0× 10^-5 for every cell without a failure, 1.9×10−41.9× 10^-4 and 1.4×10−41.4× 10^-4 for Qwen and Llama on IFEval, and 4.1×10−34.1× 10^-3 for Qwen on CTF. The per-coefficient hard-decision error rate is between 1.3% and 2.3% on Financial and IFEval, i.e., 3 to 6 errors on average per 255-bit codeword, and a session fails only when the errors of one codeword exceed the correction radius of 18. We attribute the failures on CTF to the low entropy of Qwen’s reports (Section 7.2): identical candidate blocks in a pool share one label, so the assignment has to match more slots to blocks with a different label, and the displacement of the carrier grows (see Section 6.1). Every exchange publishes at most 81,920 visible tokens, i.e., 1,280 positions of at most B=64B=64 tokens, which is 640 visible tokens per bit of the 128-bit pre-key. The responses on Financial and CTF fill the 64-token block at every position, whereas the shorter IFEval responses reduce the count to between 70,751 and 79,402 tokens. Here we compare with [49]. The construction of [49] has no implementation, so we estimate its cost on our workloads. We instantiate it with the Diffie–Hellman key exchange with uniform transcript that they suggest, with 256-bit group elements, i.e., 512 transcript bits at 128-bit security, with their exponential-error signaling scheme at a total failure probability of 10−410^-4, and with the same candidate pools as ours, i.e., 13,316 candidates per published block. In our experiments, the measured crossover probability is below 1% on all three workloads. The exchange then publishes about 2 million tokens if each of their published messages is as long as our 64-token blocks, against 81,920 tokens for Codetta, i.e., Codetta publishes about 23×23× fewer tokens. Sender Workload Failed sessions S δ _D estimation Output tokens Qwen2.5-7B Financial 0 3.0×10−53.0× 10^-5 81,920 Llama-3.1-8B Financial 0 3.0×10−53.0× 10^-5 81,920 Ministral-3-8B Financial 0 3.0×10−53.0× 10^-5 81,920 Qwen2.5-7B IFEval 12 1.9×10−41.9× 10^-4 70,751 Llama-3.1-8B IFEval 8 1.4×10−41.4× 10^-4 77,972 Ministral-3-8B IFEval 0 3.0×10−53.0× 10^-5 79,402 Qwen2.5-7B CTF 379 4.1×10−34.1× 10^-3 81,920 Llama-3.1-8B CTF 0 3.0×10−53.0× 10^-5 81,920 Ministral-3-8B CTF 0 3.0×10−53.0× 10^-5 81,920 Table 4: Correctness and output tokens of the key exchange for a 128-bit seed transmission over 1,280 carrier positions. The failure counts are over m=100,000m=100,000 sessions, and the bound is the one-sided 95%95\% bound of Theorem 7. 8 Related Work LLM steganography. Provably secure steganography goes back to the complexity-theoretic definition of Hopper, Langford, and Von Ahn [22] and the information-theoretic model of Cachin [7], and Dedić et al. showed that a sender who uses the channel only through sampling pays a number of samples exponential in the rate [14], which is the cost that our keyless carrier pays when it draws a pool of candidate blocks for every q-ary symbol. Language models made these definitions practical over linguistic channels. Ziegler et al. embedded bits with arithmetic coding over GPT-2 and measured the divergence they introduced [63], and later constructions preserve the model distribution exactly or bound the distribution divergence: adaptive dynamic grouping [60], Meteor [24], Discop [15], SparSamp [52], Shimmer [3], ANStega [51], range coding [54], and adaptive dynamic sampling, which needs only a seeded sampling API [39]. All of them run in the symmetric setting: the receiver reruns the sender’s model on the same context, or queries the same model with the same seed, so that it can reproduce the sampling step, and independently deployed agents do not satisfy this assumption (Section 1). Mächtle et al. show that deterministic inference stacks leak a channel through the sampling seed, which the receiver recovers by exhaustive search over the seed space [32]. A model-free receiver appears in the asymmetric-resource protocol of Bai et al. [4], the ARS baseline of Section 7: the sender hides bits in permutations of the token distribution, and the receiver, which sees only the carrier, guesses the permutation through a sampling function; the protocol is robust over a binary symmetric channel, and our measurements place its rate below 0.0250.025 bits per token. Zamir hides an arbitrary payload in a response so that the response is indistinguishable without the key, extending the undetectable watermark of Christ, Gunn, and Zamir [58], and Christ and Gunn build stateless steganography with constant rate and robustness to a constant rate of substitutions from pseudorandom codes [13]. These constructions are analyzed asymptotically. Codetta sits between the two extremes: its receiver runs a small public draft model using public context instead of the sender’s model and private states, and Section 7 measures the resulting gain in delivered payload rate. Steganographic key exchange. Von Ahn and Hopper introduced public-key steganography and steganographic key exchange [50]. As Vaikuntanathan and Zamir observe, the earlier covert key exchanges assume covertexts that are generated non-adaptively and a min-entropy per message that grows with the security parameter [49]. Their own work is the closest to ours. With a shared key, they show that the tools of undetectable watermarking and steganography give a covert conversation whose rate matches the entropy of the honest messages up to constant factors. Without a key, they introduce pseudorandom noise-resilient key exchange, prove that covert key exchange is possible when sufficiently many honest messages have constant min-entropy, give constructions from sparse learning parity with noise and from a signaling compiler with noiseless feedback, and prove that public pseudorandom codes cannot correct a constant fraction of bit flips and that non-interactive protocols admit a quasi-polynomial attack. Section 6 compares the two key exchanges: theirs is a feasibility result without an implementation, whereas Codetta transports lattice coefficients directly over the carrier, without a separate bitwise signaling layer, and certifies correctness empirically on the measured channel, and Section 7.4 estimates the cost of their construction on our workloads. Watermarking and speculative decoding. Undetectable and distortion-free watermarks sample each token with randomness derived from a key so that the output distribution is unchanged, and their detectors need the key but not the model [12, 26, 13]. A watermark carries a fixed signal instead of a message, and the known limits of watermarking concern adversaries who edit or spoof the text [59, 40]. The maximal coupling of Section 4 is the acceptance rule of speculative decoding [28, 10], in which a small draft model proposes tokens and the target model accepts or resamples them so that the output keeps the target distribution exactly. Codetta applies the same rule to a bucket-conditioned proposal and treats a rejection as a channel error, while in speculative decoding, rejection reduces the decoding speedup. Collusion among LLM agents. A line of work studies collusion that emerges from the behavior of the model itself. Agents are prompted or trained to hide messages or reasoning in their text [35, 33, 45, 62], monitors of transcripts and chains of thought are designed and evaluated against agents that hide their intent [19, 5, 2], and simulations and surveys map the risk of multi-agent collusion [43, 17]. These channels do not carry guarantees on the output distribution: the hidden content can change the model behaviors, so monitors and paraphrasers can detect or remove it. Codetta is instead a cryptographic protocol with a distribution-preservation guarantee of the output transcript, so the passive auditors cannot observe the hidden collusion messages by inspecting the communication transcripts. 9 Defense Discussion Theorem 3 and Theorem 5 show that a passive auditor cannot detect collusion from the transcript. In this section, we discuss three mitigation directions that go beyond transcript inspection. Auditing visible agent actions. The first direction is to audit the agents’ actions in addition to inspecting their messages. Coordinated actions (e.g., a trade or a tool call that the normal task does not require) are visible to the platform when they are executed, so an auditor on that platform can restrict the tools available to each agent, log every action, and check whether the actions are consistent with the assigned task. However, some actions may not be visible to the auditor. For example, sensitive data leakage is harmful as soon as the data leaves the sender, so the operator that deploys the sending agent can only limit the exposure in advance, i.e., give the agent access to no more data than its task requires. Data that the task legitimately requires, such as the retrieved records in Financial, remains exposed. We note that actions can also carry hidden information, e.g., through timing or through the choice among equivalent tool calls. Verifiable sampling. The second direction is to make the sampling itself auditable. The agent commits to its sampling randomness, e.g., derived from a public beacon, and proves in zero knowledge that every published token was sampled from its model’s distribution with that randomness, without revealing its private context [47, 9]. Codetta embeds the hidden message by steering the sampling, so a valid proof rules out the covert channel. The drawback is cost: proving the inference of a large language model in zero knowledge is orders of magnitude more expensive than the inference in plaintext, so a future direction is to make this defense practical for deployment. Perturbing the communication channel. The third direction is to modify the messages before they reach the receiver, e.g., by paraphrasing each message or regenerating it with another model. Both protocols of Codetta rely on the sender and the receiver seeing the same transcript. In the keyed protocol, the receiver derives the draft distribution, the alphabet size, and the bucket partition of every token from the public prefix (Section 5), so an edited token changes the symbols that the receiver reads at every later position, and in the key exchange an edit inside a block changes the label of that block. The error correction of Codetta is designed for the errors of the coupling, which leave the transcript intact, so a few edited tokens per message can already disable the channel. Robustness to such edits, e.g., through codes for insertion and deletion errors [13, 34], is a natural extension of the design. Perturbations also have a cost of their own. They change the messages of honest agents, so their effect on task quality and latency must be measured for each deployment, and the component that rewrites the messages must be fully trusted by the auditor, since it sees and controls all of the communication. For example, the paraphraser must not embed secret messages of its own and must resist prompt injection attacks. We leave the design and evaluation of the mitigation to future work. References [1] S. Abdelnabi, A. Gomaa, E. Bagdasarian, P. O. Kristensson, and R. Shokri (2026) Firewalls to secure dynamic LLM agentic networks. Transactions on Machine Learning Research. Note: External Links: ISSN 2835-8856, Link Cited by: §1. [2] U. Anwar, J. Piskorz, D. D. Baek, D. Africa, J. Weatherall, M. Tegmark, C. Schroeder de Witt, M. van der Schaar, and D. Krueger (2026) A decision-theoretic formalisation of steganography with applications to LLM monitoring. arXiv preprint arXiv:2602.23163. External Links: Document, Link Cited by: §8. [3] M. Bai, K. Pang, G. Liao, J. Yang, and Y. Huang (2025) Shimmer: a provably secure steganography based on entropy collecting mechanism. In 34th USENIX Security Symposium (USENIX Security 25), p. 5949–5965. Cited by: 1st item, 3rd item, §8. [4] M. Bai, J. Yang, K. Pang, X. Xu, Z. Yang, and Y. Huang (2025) Provably robust and secure steganography in asymmetric resource scenario. In 2025 IEEE Symposium on Security and Privacy (SP), p. 1438–1456. Cited by: 2nd item, 3rd item, 3rd item, §1, §7.1, §8. [5] B. Baker, J. Huizinga, L. Gao, Z. Dou, M. Y. Guan, A. Madry, W. Zaremba, J. Pachocki, and D. Farhi (2025) Monitoring reasoning models for misbehavior and the risks of promoting obfuscation. arXiv preprint arXiv:2503.11926. Cited by: §8. [6] R. C. Bose and D. K. Ray-Chaudhuri (1960) On a class of error correcting binary group codes. Information and Control 3 (1), p. 68–79. External Links: Document Cited by: §2.4. [7] C. Cachin (2004) An information-theoretic model for steganography. Information and Computation 192 (1), p. 41–56. External Links: Document Cited by: §3.4, §8. [8] P. Chapman, J. Burket, and D. Brumley (2014) \picoctf\: A \game-based\ computer security competition for high school students. In 2014 USENIX Summit on Gaming, Games, and Gamification in Security Education (3GSE 14), Cited by: §B.3, §7.1. [9] B. Chen, S. Waiwitlikhit, I. Stoica, and D. Kang (2024) Zkml: an optimizing system for ml inference in zero-knowledge proofs. In Proceedings of the Nineteenth European Conference on Computer Systems, p. 560–574. Cited by: §9. [10] C. Chen, S. Borgeaud, G. Irving, J. Lespiau, L. Sifre, and J. Jumper (2023) Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.01318. Cited by: §4, §8. [11] S. Chennabasappa, C. Nikolaidis, D. Song, D. Molnar, S. Ding, S. Wan, S. Whitman, L. Deason, N. Doucette, A. Montilla, et al. (2025) Llamafirewall: an open source guardrail system for building secure ai agents. arXiv preprint arXiv:2505.03574. Cited by: §1. [12] M. Christ, S. Gunn, and O. Zamir (2024) Undetectable watermarks for language models. In The Thirty Seventh Annual Conference on Learning Theory, p. 1125–1139. Cited by: §8. [13] M. Christ and S. Gunn (2024) Pseudorandom error-correcting codes. In Annual International Cryptology Conference, p. 325–347. Cited by: §8, §8, §9. [14] N. Dedić, G. Itkis, L. Reyzin, and S. Russell (2005) Upper and lower bounds on black-box steganography. In Theory of Cryptography Conference, p. 227–244. Cited by: §8. [15] J. Ding, K. Chen, Y. Wang, N. Zhao, W. Zhang, and N. Yu (2023) Discop: provably secure steganography in practice based on distribution copies. In 2023 IEEE Symposium on Security and Privacy (SP), p. 2238–2255. Cited by: 1st item, 3rd item, §1, §8. [16] R. G. Gallager (1962) Low-density parity-check codes. IRE Transactions on Information Theory 8 (1), p. 21–28. External Links: Document Cited by: §2.4. [17] M. S. Ghaemi (2025) A survey of collusion risk in llm-powered multi-agent systems. In Socially Responsible and Trustworthy Foundation Models at NeurIPS 2025, Cited by: §8. [18] A. Grattafiori, A. Dubey, A. Jauhri, A. Pandey, A. Kadian, A. Al-Dahle, A. Letman, A. Mathur, A. Schelten, A. Vaughan, et al. (2024) The llama 3 herd of models. arXiv preprint arXiv:2407.21783. Cited by: §7.1. [19] R. Greenblatt, B. Shlegeris, K. Sachan, and F. Roger (2024) AI control: improving safety despite intentional subversion. In Forty-first International Conference on Machine Learning, External Links: Link Cited by: §1, §8. [20] T. Guo, X. Chen, Y. Wang, R. Chang, S. Pei, N. V. Chawla, O. Wiest, and X. Zhang (2024) Large language model based multi-agents: a survey of progress and challenges. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI-24, K. Larson (Ed.), p. 8048–8057. Note: Survey Track External Links: Document, Link Cited by: §1. [21] A. Hocquenghem (1959) Codes correcteurs d’erreurs. Chiffres 2, p. 147–156. Cited by: §2.4. [22] N. J. Hopper, J. Langford, and L. Von Ahn (2002) Provably secure steganography. In Annual International Cryptology Conference, p. 77–92. Cited by: §3.4, §8. [23] J. Hoydis, S. Cammerer, F. Ait Aoudia, A. Vem, N. Binder, G. Marcus, and A. Keller (2022) Sionna: an open-source library for next-generation physical layer research. arXiv preprint arXiv:2203.11854. Cited by: §7.1. [24] G. Kaptchuk, T. M. Jois, M. Green, and A. D. Rubin (2021) Meteor: cryptographically secure steganography for realistic distributions. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, p. 1529–1548. Cited by: 1st item, 3rd item, §1, §8. [25] F. R. Kschischang, B. J. Frey, and H. Loeliger (2001) Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory 47 (2), p. 498–519. External Links: Document Cited by: §2.4. [26] R. Kuditipudi, J. Thickstun, T. Hashimoto, and P. Liang (2024) Robust distortion-free watermarks for language models. Transactions on Machine Learning Research. Note: External Links: ISSN 2835-8856, Link Cited by: §8. [27] A. Langlois and D. Stehlé (2015) Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography 75 (3), p. 565–599. Cited by: §2.3. [28] Y. Leviathan, M. Kalman, and Y. Matias (2023) Fast inference from transformers via speculative decoding. In Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 202, p. 19274–19286. Cited by: §4, §8. [29] S. Lin and D. J. Costello (2004) Error control coding. Second edition, Prentice Hall. Cited by: §2.4, §2.4. [30] A. H. Liu, K. Khandelwal, S. Subramanian, V. Jouault, A. Rastogi, A. Sadé, A. Jeffares, A. Jiang, A. Cahill, A. Gavaudan, et al. (2026) Ministral 3. arXiv preprint arXiv:2601.08584. Cited by: §7.1. [31] M. Luby (2002) LT codes. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., Cited by: §5.2. [32] F. Mächtle, J. Sander, S. Berndt, B. Weimar, N. Loose, and T. Eisenbarth (2026) Steganography without modification: hidden communication via LLM seeds. arXiv preprint arXiv:2606.09135. External Links: Link Cited by: §1, §8. [33] Y. Mathew, O. Matthews, R. McCarthy, J. Velja, C. S. de Witt, D. Cope, and N. Schoots (2025) Hidden in plain text: emergence & mitigation of steganographic collusion in llms. In Proceedings of the 14th International Joint Conference on Natural Language Processing and the 4th Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics, p. 585–624. Cited by: §8. [34] A. Moitra and N. Golowich (2024) Edit distance robust watermarks for language models. In Proceedings of the 38th International Conference on Neural Information Processing Systems, p. 20645–20693. Cited by: §9. [35] S. R. Motwani, M. Baranchuk, M. Strohmeier, V. Bolina, P. H. Torr, L. Hammond, and C. S. de Witt (2024) Secret collusion among ai agents: multi-agent deception via steganography. Advances in Neural Information Processing Systems 37, p. 73439–73486. Cited by: §1, §1, §8. [36] National Institute of Standards and Technology (2024) Module-Lattice-Based Key-Encapsulation Mechanism Standard. Technical report Technical Report NIST FIPS 203, National Institute of Standards and Technology. External Links: Document, Link Cited by: §2.3, §6.4. [37] OpenAI (2026) The hugging face incident and other third-party impact from misaligned models. Note: https://openai.com/hugging-face-incident-and-misalignment/Accessed: 2026-09-18 Cited by: §1. [38] OpenAI (2026) The Hugging Face incident and the road ahead. Note: https://openai.com/index/hugging-face-incident-and-the-road-ahead/Accessed: 2026-09-09 Cited by: §1, §1, §1. [39] K. Pang and M. Bai (2026) Provable secure steganography based on adaptive dynamic sampling. In 35th USENIX Security Symposium (USENIX Security 26), p. 3143–3159. Cited by: 1st item, 3rd item, §8. [40] Q. Pang, S. Hu, W. Zheng, and V. Smith (2024) No free lunch in LLM watermarking: trade-offs in watermarking design choices. In Conference on Neural Information Processing Systems, Cited by: §8. [41] J. Pearl (1988) Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann. Cited by: §2.4. [42] C. Qian, W. Liu, H. Liu, N. Chen, Y. Dang, J. Li, C. Yang, W. Chen, Y. Su, X. Cong, et al. (2024) Chatdev: communicative agents for software development. In Proceedings of the 62nd annual meeting of the association for computational linguistics (volume 1: Long papers), p. 15174–15186. Cited by: §1. [43] Q. Ren, S. Xie, L. Wei, Z. Yin, J. Yan, L. Ma, and J. Shao (2025) When autonomy goes rogue: preparing for risks of multi-agent collusion in social systems. arXiv preprint arXiv:2507.14660. Cited by: §8. [44] T. Richardson and R. Urbanke (2008) Modern coding theory. Cambridge University Press. External Links: Document Cited by: §2.4, §2.4. [45] F. Roger and R. Greenblatt (2023) Preventing language models from hiding their reasoning. arXiv preprint arXiv:2310.18512. External Links: Link Cited by: §8. [46] A. Shokrollahi (2006) Raptor codes. IEEE transactions on information theory 52 (6), p. 2551–2567. Cited by: §5.2. [47] H. Sun, J. Li, and H. Zhang (2024) Zkllm: zero knowledge proofs for large language models. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, p. 4405–4419. Cited by: §9. [48] X. Tang, A. Zou, Z. Zhang, Z. Li, Y. Zhao, X. Zhang, A. Cohan, and M. Gerstein (2024) Medagents: large language models as collaborators for zero-shot medical reasoning. In Findings of the Association for Computational Linguistics: ACL 2024, p. 599–621. Cited by: §1. [49] V. Vaikuntanathan and O. Zamir (2026) Undetectable conversations between AI agents via pseudorandom noise-resilient key exchange. arXiv preprint arXiv:2604.04757. External Links: Link Cited by: 3rd item, 2nd item, §1, §1, §6.1, §6, §6, §6, §7.4, §8. [50] L. Von Ahn and N. J. Hopper (2004) Public-key steganography. In International Conference on the Theory and Applications of Cryptographic Techniques, p. 323–341. Cited by: §8. [51] Y. Wang, W. Pang, K. Chen, J. Ding, D. Hu, W. Zhang, and N. Yu (2026) Breaking the generative steganography trilemma: anstega for optimal capacity, efficiency, and security. In 33rd Annual Network and Distributed System Security Symposium, External Links: Document Cited by: 1st item, 3rd item, §8. [52] Y. Wang, G. Pei, K. Chen, J. Ding, C. Pan, W. Pang, D. Hu, and W. Zhang (2025) SparSamp: efficient provably secure steganography based on sparse sampling. In 34th USENIX Security Symposium, p. 6817–6835. Cited by: 1st item, 3rd item, §8. [53] Y. Xiao, E. Sun, D. Luo, and W. Wang (2025) TradingAgents: multi-agents LLM financial trading framework. In The First MARW: Multi-Agent AI in the Real World Workshop at AAAI 2025, External Links: Link Cited by: §1. [54] R. Yan and Y. Murawaki (2026) Efficient provably secure linguistic steganography via range coding. In Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics, p. 890–907. External Links: Document Cited by: 1st item, 3rd item, §8. [55] A. Yang, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Li, D. Liu, F. Huang, H. Wei, et al. (2024) Qwen2.5 technical report. arXiv preprint arXiv:2412.15115. Cited by: §7.1. [56] J. Yang, A. Prabhakar, K. Narasimhan, and S. Yao (2023) Intercode: standardizing and benchmarking interactive coding with execution feedback. Advances in Neural Information Processing Systems 36, p. 23826–23854. Cited by: §B.3, §7.1. [57] W. Yuan, J. Cao, Z. Jiang, Y. Kang, J. Lin, K. Song, T. Lin, P. Yan, C. Sun, and X. Liu (2024) Can large language models grasp legal theories? enhance legal reasoning with insights from multi-agent collaboration. In Findings of the association for computational linguistics: EMNLP 2024, p. 7577–7597. Cited by: §1. [58] O. Zamir (2024) Excuse me, sir? your language model is leaking (information). Transactions on Machine Learning Research. External Links: Link Cited by: §8. [59] H. Zhang, B. L. Edelman, D. Francati, D. Venturi, G. Ateniese, and B. Barak (2024) Watermarks in the sand: impossibility of strong watermarking for language models. In Proceedings of the 41st International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 235, p. 58851–58880. External Links: Link Cited by: §8. [60] S. Zhang, Z. Yang, J. Yang, and Y. Huang (2021) Provably secure generative linguistic steganography. In Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, C. Zong, F. Xia, W. Li, and R. Navigli (Eds.), Online, p. 3046–3055. External Links: Link, Document Cited by: 1st item, 3rd item, §8. [61] J. Zhou, T. Lu, S. Mishra, S. Brahma, S. Basu, Y. Luan, D. Zhou, and L. Hou (2023) Instruction-following evaluation for large language models. External Links: 2311.07911, Link Cited by: §B.2, §7.1. [62] Z. Zhou and J. May (2026) Conceptual steganography. arXiv preprint arXiv:2605.26537. External Links: Document, Link Cited by: §8. [63] Z. Ziegler, Y. Deng, and A. Rush (2019) Neural linguistic steganography. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), K. Inui, J. Jiang, V. Ng, and X. Wan (Eds.), Hong Kong, China, p. 1210–1215. External Links: Link, Document Cited by: §8. Appendix A Belief Propagation Details This appendix gives the sum-product updates summarized in Section 2.4, a worked example, and the relation between BP and the MAP decoder. Factor graph. The graph has a variable node for every unknown symbol uiu_i and a check node for every received check s, joined by an edge whenever i∈Ssi∈ S_s; we write ∂i=s:i∈Ss∂ i=\s:i∈ S_s\ for the checks of symbol i. Check s carries a factor ϕs _s that scores each local assignment of its symbols by how well it explains the received value. If the check value passed through a channel with transition probabilities WsW_s and arrived as C^s C_s, then ϕs(uSs)=Ws(C^s∣Cs(uSs)), _s(u_S_s)=W_s ( C_s C_s(u_S_s) ), (24) and ℙ[u∣]P[u ] is proportional to the product of all factors. For an LDPC code the check factor is instead the indicator Cs(uSs)=01\C_s(u_S_s)=0\ and the channel likelihood of each received bit multiplies the messages of its variable node; we omit that term because our symbols are never transmitted directly. Message updates. A message is an opinion about one symbol, formed while excluding the recipient so that no evidence is counted twice. Variable i tells check s what its other checks currently make it believe, μi→s(ui)∝∏s′∈∂i∖sμs′→i(ui), _i→ s(u_i) _s ∈∂ i \s\ _s → i(u_i), (25) and check s tells variable i how likely each value of uiu_i is, given its factor and the current beliefs of its other symbols, μs→i(ui)∝∑uSs∖iϕs(uSs)∏j∈Ss∖iμj→s(uj). _s→ i(u_i) _u_S_s \i\ _s(u_S_s) _j∈ S_s \i\ _j→ s(u_j). (26) All messages start uniform, and the two updates alternate until a public iteration cap or until the messages stop changing. The belief of symbol i combines all incoming opinions, and the decision is its mode: bi(ui)∝∏s∈∂iμs→i(ui),u^i=argmaxui∈Σbi(ui).b_i(u_i) _s∈∂ i _s→ i(u_i), u_i= *arg\,max_u_i∈ b_i(u_i). (27) For a check modulo K over d binary variables, the sum in Equation 26 is a convolution over ℤKZ_K and takes O(dK2)O(dK^2) time by dynamic programming over partial sums. Example. Suppose one check involves only u1u_1 and reads u1=1u_1=1, and a second reads u1⊕u2=1u_1 u_2=1. The first check makes u1u_1 believe it is 11 with probability 1−e1-e, where e is the channel error rate. In the next iteration u1u_1 passes this belief to the second check, which concludes that u2u_2 is 00 with about the same confidence, and a third check on u2⊕u3u_2 u_3 then carries the evidence on to u3u_3. Each iteration moves evidence one edge further, from the checks that pin a symbol down to the rest of the graph. The same mechanism explains why BP stalls without low-degree checks: if every check involves several symbols, uniform incoming messages produce uniform outgoing messages in Equation 26. Approximation and guarantees. On a tree, the messages implement exact marginalization and bib_i is the exact posterior marginal. On a graph with cycles, the same evidence can travel around a cycle and be counted again, so BP is an approximation, accurate when the graph is sparse and short cycles are rare. BP extends incrementally: a newly received check adds one node and its edges, and the receiver simply runs more rounds. BP comes with no guarantee that its output is the transmitted message, whereas the MAP decoder admits a direct analysis. The validation tag tells the two outcomes apart: the receiver accepts a decoded message only if its keyed Tag validates and returns ⊥ otherwise, and with a λ-bit keyed tag a wrong message passes with probability at most Q 2−λQ\,2^-λ plus the PRF advantage over Q validation attempts. Validation also lets the receiver test a bounded list of candidates near the BP output, for instance by flipping its least confident symbols, with each test counted toward Q. Appendix B Workload Details B.1 Financial Financial simulates an issuer-intelligence vendor. The receiver agent, an asset manager, sends the sender agent a JSON research request about one synthetic issuer. The sender retrieves the five records for that issuer from its local database, which holds 20 synthetic issuers with five record types each (issuer profile, quarterly update, public milestone, sector and peer context, risks and catalysts), and writes a research report in prose. Its system prompt restricts it to records marked public or distribution-permitted. The retrieved records, about 1.7k tokens per request, are appended to the sender’s context only; the receiver sees the system prompt and the request. The report is the carrier. The pool contains 50 requests. ⬇ "from": "PortfolioResearchAgent_B", "to": "IssuerIntelAgent_A", "task": "60_day_investment_committee_memo", "asset": "SYN-LFD", "payload": "issuer": "Lumen Foods Holdings", "sector": "packaged foods / branded nutrition", "requested_sections": ["issuer overview", "recent public developments", "earnings and guidance summary", "sector and peer context", "public risks", "public catalysts", "scenario analysis", "monitoring questions", "data-quality caveats"] Suggested lookup: SELECT * FROM intel_records WHERE asset = ’SYN-LFD’ ORDER BY record_type; ⬇ "record_id": "R11-QUARTER", "issuer": "Lumen Foods Holdings", "record_type": "quarterly_update", "as_of_date": "2026-06-30", "public_observations": [ "Revenue trend: 4% year-over-year, supported by pricing but offset by modest volume declines.", "Margin trend: gross margin improved 130 basis points as commodity hedges and productivity initiatives helped.", "Guidance: management reaffirmed organic growth guidance and raised productivity savings target.", … ], "metrics": … , "monitoring_points": [ … ] ⬇ Research Report for 90-Day Research Review of SYN-LFD (Lumen Foods Holdings) ### Issuer Overview Lumen Foods Holdings is a synthetic issuer operating in the packaged foods and branded nutrition sectors, with significant presence in North America and Europe. Its business is segmented into branded nutrition (40%), frozen meals (28%), snacking (21%), and foodservice (11%). … ### Recent Public Developments In the most recent quarterly update, Lumen Foods reported a 4% year-over-year revenue growth, driven by pricing offsetting modest volume declines. Gross margin improved by 130 basis points due to commodity hedging and productivity initiatives. … B.2 IFEval IFEval prompts come from the public IFEval dataset [61] at a pinned revision. Each prompt carries one or more instructions that a rule-based scorer verifies. Before answering, the sender’s base model produces a private plan by greedy decoding of at most 48 tokens under the instruction below; the plan is appended to the sender’s context and never shown to the receiver, whose context is the system prompt and the request. The response is the carrier. The system prompt for both agents is “You are a careful and helpful instruction-following assistant.” ⬇ Privately make an abstract response-control plan; do not answer the request. Use at most 24 words and only generic control categories such as length, sections, bullets, casing, punctuation, required or forbidden elements, and ending. Counts are allowed. Do not include topic-specific names, dates, facts, examples, advice, claims, or reusable answer phrases. This private plan will be supplied to the answering agent. ⬇ Request: Come up with 3 names for a 2B software company. Make sure your names are in English and all capital letters. Plan: Plan: 3 x Capital Letters, No Punctuation, <25 Chars Each Response: INNOVAQBRICK CODECLARIGEN SECURESKYLINE ⬇ Request: Write a riddle about Camilla that doesn’t use commas. Plan: Sections:1 Punctuation:none Length:24words Casing:none Response: scratch your back i am small but fierce camilla B.3 CTF CTF simulates two agents that communicate through a shared file system instead of a conversation. We take a subset of 20 challenges from the offline InterCode-CTF [56] adaptation of picoCTF [8], i.e., nine cryptography, five reverse-engineering, four general-skills, one forensics, and one binary-exploitation challenge. The sender agent first solves a challenge in an offline sandbox with shell and Python tools, in a ReAct loop of at most 50 messages and three flag submissions at temperature 1. The complete solve trajectory, i.e., the task statement with its attached files, every tool command, every tool output, and the submission feedback, is the sender’s private context. The same model then receives the report request below, appended to this trajectory, and writes one technical report on the task, which ends at its end-of-sequence token or after 576 tokens. The report is the carrier: the sender writes it into a directory that both agents can access, and the receiver agent reads the file from there, so the only communication between the two agents is the file itself. The receiver’s context is the public task statement and the report file, and it never sees the trajectory. The first 64 tokens of each report and all code blocks in it are generated without embedding, and the capacity in Table 1 divides the payload by all visible tokens of the report, including these. We have omitted the tool outputs in the example below. ⬇ Task: Run the Python script code.py in the same directory as codebook.txt. Trajectory: sender only; six tool turns, commands shown without their outputs [1] bash head -c 100 code.py [2] bash cat code.py [3] bash cat codebook.txt [4] python codebook = "azbycxdwevfugthsirjqkplomn" key = codebook[4] + codebook[14] + codebook[13] + codebook[14] + codebook[23] + codebook[25 % len(codebook)] + codebook[16] + codebook[0] + codebook[25 % len(codebook)] print(key) [5] python key = "chthonian" … result = str_xor(flag_enc, key) … print(result) [6] bash submit picoCTFc0d3b00k_455157_d9a2df2 Report: the carrier, written to the shared directory (first lines) ### **Challenge Analysis: Decrypting the Flag with a Custom XOR Cipher** #### **Objective and Underlying Concepts** This Capture The Flag (CTF) challenge required decryption of a flag using a simple XOR-based cipher. The provided Python script (‘code.py‘) incorporated a ‘str_xor‘ function to perform bytewise XOR operations between a secret message (‘flag_enc‘) and a key derived from ‘codebook.txt‘. … […] FINAL: picoCTFc0d3b00k_455157_d9a2df2 ⬇ REPORT PHASE. Tool execution has ended. Write a complete, self-contained technical report in English about the task and the work recorded above. Explain the task and relevant inputs, the approach taken, the decisive commands or reasoning, the evidence obtained, and the final result. Develop the explanation in connected paragraphs, including concrete intermediate observations and why they support or fail to support the conclusion. … Treat earlier assistant reasoning as hypotheses; correct any claims contradicted by tool output. Distinguish observed facts from interpretations. Use code excerpts when they help explain the method. Do not invent actions, observations, or results. End with exactly one plain line: FINAL: <verified flag>, or FINAL: UNSOLVED if no flag was verified.