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).
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:
- Prefix Forest Construction: It organizes all candidate tokens into a "prefix forest" where a token is a child of its longest proper prefix.
- 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.
- 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.
- 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.
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.
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
float64to 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