A Proof That Hiding Messages in AI Text Has an Unavoidable Tax — and a Scheme That Pays Only That Tax

Proves a tight lower bound on capacity loss from tokenization ambiguity in linguistic steganography, then builds a scheme that hits the bound. 91-93% entropy retention, 2-7× gain over prior art.

Imagine you and a friend agree to communicate by mailing Scrabble tiles. You pick tiles from a bag to spell words that encode a secret, but the postman delivers only the printed letters — the physical tiles (with their point values and blanks) are stripped away. If two different tiles can print the same letter, your friend can't be sure which tile you drew, and some of your secret leaks into resolving that ambiguity. This paper asks: exactly how much capacity do you lose to that ambiguity, and can you lose nothing more? The core claim is a tight impossibility result for linguistic steganography — the art of hiding secret messages inside AI-generated text that looks like ordinary language. Modern language models operate on tokens (subword chunks), but a text channel delivers characters. Multiple tokenizations can produce the same string: 'unbelievable' might be one token or three. If sender and receiver disagree on which tokens produced a text, extraction fails. Prior fixes either changed the output distribution (detectable), synchronized enormous token pools (capacity collapse at large vocabularies), or tracked multiple decoding histories (exponential blowup). Jiang proves that any single-history receiver achieving exact extraction across full-support language models is confined to a prefix-free candidate set at every step. The key quantity lost is 'stop entropy' — the information content of deciding whether a prefix token terminates at a given character boundary. This is a structural bound: no clever engineering can recover it, even if the receiver reads the entire future text. The proof holds regardless of what constraints the sender imposes on later steps. The constructive half delivers 'coin projection,' a closed-form scheme that exactly achieves this bound. It fixes stop decisions on the prefix forest using shared randomness, works with any distribution coder in a single model call per token, and preserves the model's sampling distribution — critical for undetectability. The scheme refines SyncPool (the previous best approach) at every vocabulary size. Empirical results across English, Chinese, and Japanese show that tokenization ambiguity is rare in raw frequency — at most 11 ambiguous positions per 1,000 tokens. But the stop entropy at those positions is expensive: 7.2-9.0% of per-step entropy. SyncPool loses even more because space characters and single-byte UTF-8 hub tokens merge entire subtrees while carrying almost no stop uncertainty — a structural inefficiency coin projection avoids. The result: coin projection retains 91-93% of string entropy for the coder at every vocabulary size, and with the full vocabulary converts 2.16-6.85 times as much entropy into message bits as SyncPool. The integrity picture is strong for a theory paper: the main result is a mathematical proof (impossibility + achievability), and the empirical evaluation spans three typologically distinct languages. The baselines are current — SyncPool is the named prior art. What's missing is an adversarial detectability evaluation against trained steganalysis models; the paper's security claim rests on the provable distribution-preservation property rather than empirical evasion tests. The practical upshot: if you're building covert communication channels over AI text, this paper tells you the exact price of tokenization ambiguity and gives you a scheme that pays only that price. The 2-7× capacity gain over SyncPool is not incremental — it changes what message lengths are practical. The gap between 'provably secure' and 'undetected by real adversaries' remains the field's next load-bearing question.