The Capacity-Stealthiness Trade-Off in Linguistic Steganography

25 concepts17 papers1 proposal

Linguistic steganography is the art of hiding secret messages inside ordinary, natural language text. Unlike cryptography, which scrambles a message to make its contents unreadable, steganography conceals the very existence of the communication. The ideal "stegotext" should look entirely innocent to both automated statistical detectors and human readers.

However, building a practical steganographic system reveals a fundamental tension: payload capacity versus imperceptibility. If you want to transmit a large amount of data (a high payload), you must frequently alter the text's structure or word choices. But every time you force a specific word or phrase to encode a bit sequence, you restrict the natural variance of language, leaving statistical artifacts that expose the hidden channel.

The Two Paradigms: Edit vs. Generation

To understand why this trade-off occurs, we must look at how data is embedded into text. Historically, methods have fallen into two categories: modification-based (edit-based) and generation-based.

Modification-based steganography starts with an existing human-written text and alters it to encode data. For instance, Chang and Clark explored substituting words with contextual synonyms (Practical Linguistic Steganography Using Contextual Synonym Substitution and Vertex Colour Coding) or automatically generating paraphrases (Linguistic Steganography Using Automatically Generated Paraphrases). They later extended this to permuting word order (The Secret’s in the Word Order: Text-to-Text Generation for Linguistic Steganography). More recently, Ueoka et al. utilized Masked Language Models (MLMs) like BERT to substitute words seamlessly (Frustratingly Easy Edit-based Linguistic Steganography with a Masked Language Model).

Because these methods preserve the backbone of human-authored text, they offer excellent stealth. However, as noted by Yang et al. (Semantic-Preserving Linguistic Steganography by Pivot Translation and Semantic-Aware Bins Coding), modification-based techniques hit a strict capacity ceiling because only a fraction of words can be altered without destroying the original meaning or introducing grammatical errors.

Generation-based steganography, by contrast, generates text from scratch using a language model. At each step, the model outputs a probability distribution over its vocabulary. The steganographic algorithm partitions or maps this vocabulary into "bins" representing bit sequences. By selecting the word that corresponds to the secret bits, the system generates text while simultaneously encoding data.

Early neural approaches by Jaggi et al. used LSTMs to achieve massive capacity gains (Generating Steganographic Text with LSTMs), and Deng et al. scaled this to large autoregressive models like GPT-2 using arithmetic coding (Neural Linguistic Steganography). While generation-based methods offer a much higher bits-per-word ratio, they are highly vulnerable to detection because the act of encoding bits distorts the model's natural probability distribution.

The Mimicry Gap: Statistical vs. Perceptual Imperceptibility

Why exactly does high payload capacity compromise security? The breakdown happens across two distinct dimensions: statistical and perceptual.

Statistical Imperceptibility

Statistical imperceptibility requires that the generated stegotext matches the exact probability distribution of the underlying language model. If an algorithm aggressively encodes bits, it is frequently forced to choose lower-probability tokens to satisfy the bit sequence. As Huang et al. demonstrate, this distorts the distribution, creating statistical anomalies that an automated detector can easily flag (OD-Stega: LLM-Based Near-Imperceptible Steganography via Optimized Distributions).

Conversely, simply picking the highest-probability words is also unsafe. As Yang et al. point out, human language does not always follow the most predictable path; failing to mimic the natural variance and probability fluctuations of a language model makes the text look suspiciously uniform and machine-generated (A Generation-based Text Steganography by Maintaining Consistency of Probability Distribution).

Perceptual Imperceptibility

Perceptual imperceptibility concerns how natural the text appears to a human reader. Even if text mathematically mimics a language distribution, pushing the bits-per-word ratio too high often results in repetitive, awkward, or nonsensical phrasing. Lin et al. identify this as a gap between statistical metrics and human perception: text can pass automated checks but still feel "uncanny" or jarring to a human reader (Zero-shot Generative Linguistic Steganography). Chen et al. emphasize that balancing both machine-level and human-level imperceptibility remains the core challenge of generative steganography (Enhancement of the Generation Quality of Generative Linguistic Steganographic Texts by a Character-Based Diffusion Embedding Algorithm (CDEA)).

Pushing the Frontier: Optimization and Adaptation

To maximize payload capacity without crossing the threshold of detectability, researchers have shifted from rigid vocabulary binning to adaptive, mathematically optimized distribution shaping.

Adaptive Encoding

One intuitive solution is to dynamically adjust when and how much data is hidden based on the local context. For example, Dai and Cai introduced the patient-Huffman algorithm, which deliberately chooses not to encode bits when the language model is highly certain about the next word (Towards Near-imperceptible Steganographic Text). By sacrificing capacity in highly predictable contexts, they prevent glaring statistical anomalies. Similarly, Ji et al. developed Self-Adjusting Arithmetic Coding (SAAC), which dynamically alters the size of the candidate word pool at each step to maintain a tight balance between information density and statistical naturalness (Near-imperceptible Neural Linguistic Steganography via Self-Adjusting Arithmetic Coding).

Constrained Optimization

Recent frameworks formalize this trade-off as a constrained optimization problem. Instead of treating token selection as a series of isolated choices, Tian et al. model the generation process as a Constrained Markov Decision Process (CMDP) (Relatively-Secure LLM-Based Steganography via Constrained Markov Decision Processes). By accounting for long-term token dependencies, they derive an optimal "water-filling" strategy that maximizes payload capacity while ensuring that the generated text remains statistically indistinguishable from the true language distribution.

This mathematical framing, also explored by Huang et al., proves that techniques like temperature scaling and controlled vocabulary biasing—such as the partitioning methods proposed by Silva et al. (Look Who's Talking Now: Covert Channels From Biased LLMs)—can be optimized to achieve the theoretical limit of data capacity for a given security budget.

Multi-Granularity Embedding

Alternatively, researchers look to spread the payload across multiple linguistic dimensions. Ou et al. broke through the capacity ceiling of modification-based methods by jointly manipulating both sentence structure (syntax) and word choices (lexis) (Promising Multi-Granularity Linguistic Steganography by Jointing Syntactic and Lexical Manipulations). By distributing the information payload across multiple granularities, they minimize the distortion within any single domain, allowing for higher data density without sacrificing naturalness.

Key Foundational Work

The Secret’s in the Word Order: Text-to-Text Generation for Linguistic Steganography (2012) — contributed 4 concept elements to this direction.
Linguistic Steganography Using Automatically Generated Paraphrases (2010) — contributed 2 concept elements to this direction.
Adjective Deletion for Linguistic Steganography and Secret Sharing (2012) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 17 papers
  2. Version 1 · 2026-10-04 · 19 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_steganographic_payload_capacity_ac1e4a40,
  title = {steganographic payload capacity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/steganographic-payload-capacity/rdr_ac1e4a401fdd46f6b3be7f466d40a681},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 2, frozen text):

@misc{lacuna_steganographic_payload_capacity_ac1e4a40_v2,
  title = {steganographic payload capacity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/steganographic-payload-capacity/rdr_ac1e4a401fdd46f6b3be7f466d40a681/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake