Optimal Single-History Tokenization Disambiguation for Provably Secure Linguistic Steganography

Feng JiangarXiv 2026 · arXiv

TL;DR

This paper introduces coin projection, a novel method for provably secure linguistic steganography that solves the "tokenization ambiguity" problem. By using shared randomness to pre-decide whether a token ends at a given prefix, it achieves the theoretical maximum message capacity for any single-history receiver while maintaining perfect security and requiring only one model call per token.

What Problem Does This Paper Address?

Provably secure linguistic steganography hides secret messages within text generated by Large Language Models (LLMs). To remain "provably secure," the generated text must follow the LLM's original probability distribution exactly, so a "warden" (an eavesdropper) cannot distinguish it from normal output.

The core challenge is tokenization ambiguity. LLMs operate on tokens, but communication channels carry raw text. A single string of text can often be tokenized in multiple ways. For example, the string " weekend" might be one token (weekend) or two tokens ( + weekend).

Tokenization ambiguity example: "week" vs "weekend"

If a sender uses a specific token sequence to encode a message, but the receiver's tokenizer chooses a different sequence for the same text, the message is lost. Previous solutions either compromised security by changing the model's distribution, suffered from massive capacity drops in large vocabularies (like the SyncPool method), or were computationally expensive.

Methods

The authors first prove a theoretical bound: any exact, zero-error steganography scheme using a single token history must give up the stop entropy ($H_{stop}$). This is the entropy associated with deciding, for every candidate token that is a prefix of another, whether the token ends there or continues.

Their proposed solution, Coin Projection, works as follows:

  1. Prefix Forest Construction: It organizes all candidate tokens into a "prefix forest" where a token is a child of its longest proper prefix.
  2. Shared Randomness ("Coins"): Using a secret key shared between sender and receiver, the algorithm generates "stop coins" for every node in the forest. These coins pre-determine whether a token would stop at that point if reached.
  3. Survivor Law: This process creates a "prefix-free" set of surviving candidates. Because no survivor is a prefix of another, the receiver can uniquely re-tokenize the text without error.
  4. Distributional Coding: The message is then encoded using only the remaining entropy (the choice of which "tree" to enter and which "branch" to take), ensuring the final output still matches the LLM's original distribution.

Datasets

The authors evaluated their method across three languages using standard C4 continuation benchmarks:

  • English: Llama-3.2-3B (128k vocabulary).
  • Chinese: Qwen3-4B-Base (152k vocabulary).
  • Japanese: llm-jp-3-3.7b (100k vocabulary).

They compared Coin Projection against several baselines, including "Native" (no disambiguation), "Filters" (which change the distribution), and "SyncPool."

Key Insights and Ideas

  • The Cost of "Hub" Tokens: Previous methods like SyncPool collapsed in capacity because "hub" tokens (like a bare space or common UTF-8 lead bytes) would merge thousands of candidates into a single pool. Coin Projection avoids this because it only pays the cost of uncertain boundaries (lexical prefixes), not the entire branch structure.
  • Rarity vs. Cost: While ambiguous tokenization is rare in actual generated text (occurring in fewer than 1.1% of tokens), the potential for ambiguity exists at almost every step in the model's candidate pool. This "stop entropy" consistently accounts for 7–9% of the total available entropy.
  • Optimality: The paper proves that Coin Projection is not just a good heuristic; it is theoretically optimal for receivers that maintain a single token history.
Figure 2: Stop entropy stays at 7–9% of the string entropy at every vocabulary size, while hub tokens collapse the root entropy that SyncPool encodes. Each bar splits the string entropy Hstr of the top-k law into Hroot+Hbranch+Hstop (Lemma 1), averaged over 3,200 states of ordinary sampling (50 contexts × 64 tokens); Hhom < 10−4 bits throughout. Coin projection encodes the root and branch parts; SyncPool encodes only the root part.

Key Results

  • Massive Capacity Gains: At full vocabulary sizes, Coin Projection provides 2.16x to 6.85x more message capacity (bits per token) than SyncPool.
  • High Efficiency: It retains 91–93% of the available string entropy for message encoding across all tested languages and models.
  • Zero Error: Unlike "Native" sampling, which lost 5–10% of messages due to re-tokenization errors, Coin Projection recovered 100% of completed messages bit-for-bit.
  • Low Overhead: The computational cost is minimal, taking roughly 12–28ms per step on a CPU, which is comparable to or faster than the LLM's own forward pass.
Comparison of Filter, SyncPool, and Coin Projection logic

Limitations and Future Work

  • The $H_{stop}$ Tax: A single-history receiver must pay the stop entropy tax. To recover that final 7–9% of capacity, a receiver would need to track multiple possible tokenization histories simultaneously, which significantly increases computational complexity.
  • Floating-Point Precision: The method relies on bit-exact agreement between the sender and receiver's floating-point calculations. While the authors used float64 to mitigate this, hardware-level differences in math operations could still pose a challenge for deployment.
  • Message Length Leakage: Like most provably secure schemes, this work focuses on the distribution of the content but does not analyze whether the length of the hidden message might leak information to a sophisticated warden.

Summary updated

Abstract

Provably secure linguistic steganography assumes that the receiver recovers the sender's tokens, but a text channel delivers only text, and ambiguous tokenizations break extraction. Existing fixes change the distribution, synchronize whole pools of tokens at a capacity that collapses with large vocabularies, or track several token histories. We prove that if extraction is exact and error-free across full-support language models, a single-history receiver is confined to a prefix-free candidate set at every step -- even if it reads the entire future text and the sender constrains later steps -- and must therefore give up the stop entropy, the entropy of deciding whether each prefix token ends there. Fixing these stop decisions on the prefix forest with shared randomness yields coin projection: a closed-form scheme that attains the bound, works with any distribution coder in one model call per token, preserves ordinary sampling, and refines SyncPool for every key. Across English, Chinese and Japanese, ambiguous text is rare (at most 11 in 1,000 tokens), yet the stop entropy at word and morpheme prefixes takes 7.2-9.0% of the entropy at every step; SyncPool's further loss comes from space and single-byte UTF-8 hubs that merge subtrees while carrying almost no stop uncertainty. Coin projection keeps 91-93% of the string entropy for the coder at every vocabulary size; with the full vocabulary, it turns 2.16-6.85 times as much entropy into message bits as SyncPool and recovers every completed message.
BibTeX
@misc{jiang2026optimal,
  author = {Feng Jiang},
  title = {{Optimal Single-History Tokenization Disambiguation for Provably Secure Linguistic Steganography}},
  year = {2026},
  eprint = {2611.17091},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.17091},
}
Figure