Skip to main content
Back to timeline
arXivSource publication:

Tokenization ambiguity no longer sinks single-history steganography: coin projection keeps over 90% of string entropy at full vocabulary

Synopsis

Provably secure linguistic steganography assumes the receiver recovers the sender's tokens, but a text channel delivers only text, and one text admits many tokenizations, so retokenizing can lose the message. SyncPool kept the distribution exact by encoding pools of prefix-related tokens, yet its capacity collapsed at full vocabulary as whitespace and UTF-8 lead-byte hubs merged subtrees. Coin projection fixes each prefix's stop decision with shared randomness and leaves only root and child choices to the coder; on 3–4B models in English, Chinese and Japanese it leaves 91–93% of string entropy to the coder and turns 2.16–6.85 times as much entropy into message bits as SyncPool at full vocabulary, with zero error.

Source-provided article image: Optimal Single-History Tokenization Disambiguation for Provably Secure Linguistic Steganography
arXiv

Interpretation

Linguistic steganography can hide a message in text sampled from a language model so that no warden without the key can tell it from ordinary output, but a real channel carries only text, and retokenizing can yield a different token sequence, losing the message. Earlier fixes took three routes: filters drop candidates so the text parses uniquely, at the cost of changing the distribution security rests on; SyncPool keeps the distribution exact but merges prefix-related tokens into pools whose capacity collapses as the vocabulary grows; multi-history schemes keep nearly all the entropy but call the model several times per step. On Llama-3.2-3B, from top-16 to the full vocabulary, the largest prefix tree holds 62% to 88% of the probability on average, the bare space alone produces 62–89% of the stop entropy, and SyncPool's share of string entropy falls from 80.4% to 14.1%.

Coin projection hands each prefix's stop-or-continue decision to randomness shared by sender and receiver, so the coder only chooses among roots and children and ordinary sampling is preserved. The scheme realizes those stop decisions on the prefix forest as a closed-form construction that works with any distribution coder, needs one model call per token, and refines SyncPool's coder input for every key. On C4 continuations with Llama-3.2-3B for English, Qwen3-4B-Base for Chinese and llm-jp-3-3.7b for Japanese, 50 prompts of 64 tokens per setting, ambiguous text is at most 11 tokens in 1,000, while stop entropy at word and morpheme prefixes takes 7.2–9.0% of the per-step entropy.

At full vocabulary, coin projection leaves most of the string entropy to the coder in all three languages and recovers every completed message. In the same setting SyncPool's utilization falls to 12.9% on English, 43.3% on Chinese and 33.3% on Japanese, while coin projection keeps 88.1%, 93.6% and 89.5%. In paired 128-bit-message experiments at temperature 1, coin projection's median utilization reaches 92% of Native's and 93% of Stepwise's, matching the 91–93% of string entropy the theory leaves.

Perspective

The result covers online, single-history, zero-error schemes that are exact across all full-support language models; experiments are limited to three 3–4B base models, three languages and two tokenizer families, with 128-bit messages at temperature 1.

The stop entropy is still paid, measured at 7.2–9.0% of the entropy; exceeding that budget requires multiple histories or nonzero divergence. At full vocabulary the projection takes 28.0 ms per step on CPU against 17.8 ms for the 3B model's forward pass, and bit-exact agreement relies on a fixed computation order. Extraction has not been measured end to end beyond 4B parameters.