Hidden Information Through Synonym and Word-Choice Encoding

Executive summary#

Linguistic steganography attempts to communicate a message while concealing not only the message content but the fact that a hidden channel exists. A particularly intuitive construction assigns information to alternative natural-language realizations: for example, “large” may encode 0 and “big” may encode 1, or several paraphrases may encode multi-bit symbols. The basic idea has deep antecedents in concealment ciphers and binary carriers, but practical synonym-based systems appeared in the modern literature in the late 1990s and 2000s, followed by neural language-model systems that encode information directly through next-token generation. source

The central technical result is that capacity, naturalness, reliability, and detectability are inseparable. For a binary synonym pair, one usable choice carries at most one raw bit; if only a fraction \(q\) of words can safely be altered, the raw capacity is approximately \(q\) bits/word. Context-sensitive filtering makes the text more natural but reduces \(q\). Chang and Clark's contextual synonym system illustrates the practical regime: roughly two usable carriers per sentence, guaranteeing at least one bit per carrier, with human naturalness scores of 3.33/4 for system-modified sentences versus 3.67/4 for originals. Earlier lexical-substitution systems averaged only about 0.67 bits/sentence, while the older T-Lex dictionary provided about 0.1 bits/sentence. source

Neural generation changes the scale. Instead of choosing among literal dictionary synonyms, an encoder can choose among the entire high-probability next-token distribution. Generation-based systems have commonly operated in the approximate range of 1–5 bits/word, although the highest payloads generally increase statistical distortion or reduce linguistic quality. Ziegler, Deng, and Rush's neural arithmetic-coding approach explicitly tried to sample according to a language model while consuming hidden bits; Shen, Ji, and Han's self-adjusting arithmetic coding subsequently reported a 15.3% improvement in bits/word and 38.9% improvement in their KL-divergence metric over prior systems across four datasets, while 51% of generated covers fooled human eavesdroppers in their evaluation. source

A useful distinction is between surface-symbol channels and semantic channels. Synonym choice, token bins, spelling, punctuation, and keyed token sets are surface channels; ordinary paraphrasing can often destroy them. Prompt-based LLM channels can instead encode information through stylistic decisions, reasoning patterns, selected facts, entities, or high-level concepts. Roger and Greenblatt found that an LLM paraphrasing defense drove nearly all of their tested surface-oriented schemes below two recoverable bits per answer, corresponding to their headline bound of roughly three bits per kilobyte under the tested defense. More recent work on “conceptual steganography” demonstrates why this is not a universal defense: information encoded in higher-level reasoning behavior can survive meaning-preserving paraphrases substantially better than lexical keyword channels. source

“Natural to a human” does not imply “statistically undetectable.” Wilson, Blunsom, and Ker found that individual one-bit CoverTweet samples were close to chance for an automatic detector—AUC 0.551 for automatic CoverTweet and 0.509 for human-filtered CoverTweet—but pooling 100 tweets from one source increased automatic CoverTweet AUC to 0.9631. Likewise, a 2026 attack on theoretically distribution-preserving neural schemes reported 86.95% detection accuracy against arithmetic coding by exploiting finite-precision artifacts, while several semantic steganalysis baselines remained around chance in that experiment. source

The strongest general security objective is therefore not low perplexity or high human ratings but distributional indistinguishability. Cachin formalized passive steganalysis as hypothesis testing between cover and stego distributions and quantified security through relative entropy; Hopper, Langford, and von Ahn later formalized computational indistinguishability. In practice, exact equality of distributions is difficult because candidate filtering, finite precision, tokenization, model-version drift, prompt effects, and repeated use all create observable structure. source

The empirical literature strongly suggests the following ordering:

The numerical entries come from distinct experiments and must not be treated as a leaderboard because texts, domains, detectors, payload definitions, models, and adversary knowledge differ. source

Scope, assumptions, and formal model#

Because the question does not specify language, genre, text length, or adversary, this report assumes English prose, primarily news, web, social-media, or question-answer text, with sentences averaging roughly 20 words only when an illustrative conversion between bits/word and bits/sentence is required. Published results retain their authors' original units rather than being silently normalized. The threat model is a passive “warden” who observes text and tries to decide whether it contains a covert payload; robustness analysis additionally considers an active warden who may paraphrase, translate, edit, truncate, or otherwise transform text before delivery. This passive-adversary framing follows the information-theoretic steganography model introduced by Cachin and the computational formulation of Hopper, Langford, and von Ahn. source

Let \(X\) denote ordinary cover text distributed according to \(P_C\), \(M\) a hidden message, \(K\) a shared secret, and

\[
Y = E_K(X,M)
\]

the transmitted stegotext. The intended receiver computes

\[
\hat M=D_K(Y).
\]

Three objectives should be separated:

\[
\text{Reliability:}\qquad P[\hat M\neq M]\rightarrow 0,
\]

\[
\text{Stealth:}\qquad P_S \approx P_C,
\]

and

\[
\text{Utility:}\qquad U(Y)\approx U(X),
\]

where \(P_S\) is the distribution induced by the steganographic encoder and \(U\) represents grammaticality, semantic fidelity, task correctness, factuality, style, or another application-specific criterion. Information-theoretic and computational steganography explicitly distinguish successful decoding from indistinguishability to the observer. source

For a synonym carrier \(i\) with \(M_i\) safely interchangeable realizations, its naïve raw capacity is

\[
c_i=\log_2 M_i.
\]

For \(N\) transmitted words,

\[
R_{\rm raw}=\frac{1}{N}\sum_{i\in\mathcal C}\log_2 M_i
\quad\text{bits/word},
\]

where \(\mathcal C\) contains only positions judged safe for substitution. In the simple binary case \(M_i=2\), if a fraction \(q\) of words are usable,

\[
R_{\rm raw}=q \ \text{bits/word}.
\]

Thus a text with 20 words/sentence and \(q=0.10\) has a naïve ceiling of approximately two bits/sentence—remarkably close to the empirical regime of Chang and Clark's carefully filtered synonym system. source

There is an important complication: natural synonyms are almost never equiprobable. Suppose contextual usage predicts

\[
P_C(\text{large})=0.9,\qquad P_C(\text{big})=0.1.
\]

Encoding an unbiased message with the naïve rule large=0, big=1 forces both words toward probability 0.5. The stego distribution is then visibly distorted:

\[
D_{\mathrm{KL}}(P_S\Vert P_C)
=
\sum_xP_S(x)\ln\frac{P_S(x)}{P_C(x)}
\approx0.511\text{ nats}
\]

for this single carrier. By contrast, the entropy of the natural choice itself is only

\[
H(0.9,0.1)\approx0.469\ \text{bits}.
\]

This is the fundamental motivation for probability-matched arithmetic coding: one cannot generally extract a full covert bit from a highly skewed natural choice while preserving its natural frequency distribution. Neural steganographic systems based on arithmetic coding explicitly exploit next-token probabilities rather than forcing equiprobable token partitions. source

Historical evolution of linguistic steganography#

The conceptual lineage predates synonym substitution by centuries. Johannes Trithemius's Steganographia, written around the end of the fifteenth century and subsequently printed in the early seventeenth century, is the canonical early European work associated with concealed communication; surviving historical scans provide the primary artifact. Francis Bacon's De Augmentis Scientiarum described the biliteral cipher in 1623, encoding symbols through two distinguishable forms. Bacon's carrier was typographic rather than lexical, but structurally it is exactly the same abstraction as “synonym A = 0, synonym B = 1”: an innocuous carrier offers two externally legitimate realizations that map to a binary alphabet. source

A null cipher instead hides the message in selected positions within otherwise non-secret-looking material—for example, selected initial letters or every \(k\)-th word—while the remaining symbols are “nulls.” Its important conceptual contribution is separation between cover content and carrier positions. Modern word-choice systems preserve that principle but make the selected positions linguistically modifiable rather than merely extracting predetermined characters. Historical cryptologic literature contains both nulls inserted to disrupt cryptanalysis and concealment systems in which only selected parts of an overt text contribute to the secret channel. source

The computational lineage becomes much clearer in the 1990s. Chapman and Davida's 1997 Hiding the Hidden transformed ciphertext into innocuous generated text using dictionaries, writing-style simulation, and context-free grammars. Keith Winstein's 1998 Lexical Steganography Through Adaptive Modulation of the Word Choice Hash and its T-Lex implementation directly operationalized lexical alternatives as carriers. source

By the 2000s, researchers increasingly recognized that a thesaurus is not sufficient: “synonyms” are context sensitive, differ in collocation and register, and may correspond to multiple senses. Bolshakov therefore proposed collocationally verified synonymy; Topkara and colleagues investigated ambiguity and resilience; Chang and Clark later used very large n-gram statistics plus a graph-based coding procedure to ensure that candidate substitutions were plausible in context and decodable despite polysemy. source

The transition from editing a human cover to generating the cover itself occurred with statistical and neural language models. By 2019–2021, arithmetic coding, probability partitioning, self-adjusting coding, and masked-language-model editing let the carrier be selected from contextual token distributions rather than static synonym lists. Recent LLM research has expanded the carrier again—from tokens to prompts, semantic entities, reasoning strategies, and abstract concepts. source

timeline
    title Evolution of linguistic steganography
    1499–1606 : Trithemius — Steganographia
    1623 : Bacon — biliteral two-form carrier
    1997 : Chapman & Davida — innocuous text generation
    1998 : Winstein — T-Lex lexical word-choice hashing
    2004–2006 : Collocation-aware synonym substitution
               : Topkara ambiguity/resilience methods
    2010 : Automatically generated paraphrase carriers
    2014 : Contextual synonym substitution + vertex coding
    2019 : Neural LM + arithmetic coding
    2020 : Self-adjusting arithmetic coding
    2021 : Masked-LM editing
         : Distribution-preserving generative coding
    2023 : Prompt-based LLM channels and paraphrasing defenses
    2024–2025 : Semantic-space and embedding-assisted methods
    2026 : Conceptual reasoning channels
         : Finite-precision steganalysis

The post-1990s milestones above correspond directly to the original papers or publisher records for Chapman–Davida, Winstein, Chang–Clark, Ziegler et al., Shen et al., Ueoka et al., Zhang et al., Roger–Greenblatt, Bai et al., and the 2026 conceptual and finite-precision work. source

Modern methods and algorithmic constructions#

Contextual synonym substitution. The simplest practical encoder begins with a cover sentence, finds positions having semantically interchangeable words, filters alternatives according to syntax and contextual likelihood, and associates surviving alternatives with binary strings. Chang and Clark's system used Google n-gram evidence to check substitutions and a vertex-coding construction to resolve synonym sets that overlap because of polysemy. Their results illustrate why the filter is critical: aggressive five-gram/context filtering reached 100% precision for accepted paraphrases in an earlier system but only 4.1% recall, explicitly exchanging payload for linguistic plausibility. source

A keyed generic construction can be represented as:

SYNONYM-ENCODE(cover, bits, key):
    output ← cover
    for each candidate word position i:
        C ← contextually_valid_alternatives(output, i)

        remove candidates that:
            change the intended word sense
            violate syntax/collocation
            change named entities or factual content
            have contextual probability below threshold

        if |C| < 2:
            continue

        order C deterministically using PRF(key, context, candidate)
        b ← floor(log2 |C|)
        retain a decodable subset of size 2^b

        payload ← next b secret bits
        output[i] ← C[index(payload)]

    return output

The receiver repeats the same contextual candidate-generation and keyed ordering and maps the observed realization back to its bit index. The hard part is not the binary mapping but ensuring that sender and receiver reconstruct exactly the same candidate set. Chang and Clark's polysemy treatment and Ueoka et al.'s later discussion of tokenization inconsistency both arise from this synchronization requirement. source

Paraphrase selection. Instead of changing one word, a system can generate several semantically equivalent sentence realizations and associate them with bins. Chang and Clark's 2010 system automatically evaluated candidate paraphrases using Google n-grams and a CCG parser; their proposed embedding procedure has a theoretical maximum of one bit/sentence when every sentence is paraphrasable. source

PARAPHRASE-SELECT(sentence, message_bits, key):
    P ← generate_semantically_equivalent_paraphrases(sentence)

    P ← filter_by_grammar_semantics_and_fluency(P)

    for p in P:
        bin[p] ← HMAC(key, canonicalize(p)) mod 2^b

    target ← next b message bits
    candidates ← {p in P : bin[p] = target}

    if candidates is empty:
        emit sentence without payload
    else:
        emit highest-quality member of candidates

This construction is conceptually attractive because the carrier is a full sentence rather than a visibly unusual word. Its weakness is that paraphrasing by a third party may simply choose another member of the semantic equivalence class and thereby destroy the encoded bin.

Discrete next-token mapping. Neural generation replaces a dictionary with the language model's conditional distribution

\[
p_t(v)=P_\theta(v\mid x_{<t}).
\]

A basic construction partitions high-probability candidates into \(2^b\) bins and consumes \(b\) message bits to select a bin. The generator then chooses a plausible token from the corresponding bin. Earlier neural systems used variants of this idea; Zhang et al.'s 2021 ADG work explicitly addressed the statistical mismatch created when token partitions do not respect the model distribution. source

TOKEN-BIN-GENERATE(prompt, bits, key, LM):
    prefix ← prompt
    while bits remain:
        p ← LM.next_token_distribution(prefix)
        C ← truncate_low_probability_tokens(p)

        partition C into keyed bins B0 ... B(2^b - 1)
        j ← integer(next b bits)

        token ← probability_weighted_choice(Bj)
        append token to prefix
    return generated suffix

A plain equal-bin design is efficient but usually changes the probability with which tokens appear, particularly if high-probability tokens cluster unevenly across bins. This creates detectable n-gram and likelihood distortions. Distribution-aware partitioning reduces that leakage. source

Arithmetic-coding generation. A stronger idea treats the secret bitstream as a point \(u\) in an interval and partitions the current interval according to the LM's next-token probabilities. If the partitions are implemented ideally, selecting the token containing \(u\) samples tokens in proportion to the LM distribution.

ARITHMETIC-STEGO(bits, prompt, LM):
    u ← binary_fraction(bits)
    interval ← [0, 1)
    text ← prompt

    repeat:
        p ← LM.next_token_distribution(text)
        subintervals ← partition(interval, widths proportional to p)

        token ← unique token whose subinterval contains u
        emit token
        interval ← subinterval(token)

        renormalize interval and consume determined bits

    until payload complete

Decoding repeats the same probability calculations and progressively determines the interval containing the received token sequence. Ziegler et al. showed that arithmetic coding offered especially small distributional divergence among the neural schemes they compared, and Shen et al.'s SAAC dynamically adjusts the coding distribution to improve the capacity–imperceptibility tradeoff. source

This method is theoretically elegant but unusually sensitive to implementation consistency. Sender and receiver need the same tokenizer, LM weights, numeric operations, probability truncation, generation history, and coder. A 2026 steganalysis paper demonstrates that even finite floating-point precision can generate detectable “low-probability vanishing” artifacts despite an idealized proof of distribution matching. source

Masked-LM editing. Ueoka, Murawaki, and Kurohashi returned to the cover-editing paradigm with BERT-like masked language models. Alice masks selected tokens in an existing cover; the model proposes context-conditioned alternatives; bit strings are assigned to sufficiently probable alternatives; Bob shares the masked LM, masking rule, and encoding strategy and reconstructs the choices. source

Their directly controlled comparison is informative: the BERT editing configuration achieved 0.204 bits/word and automatic detector accuracy 0.586, whereas a GPT-2 generation baseline achieved 1.67 bits/word but detector accuracy 0.819. Lower detection accuracy is better for the steganographer. source

xychart-beta
    title "Payload and automatic detectability in Ueoka et al. (2021)"
    x-axis ["BERT edit: 0.204 b/w", "GPT-2 generation: 1.67 b/w"]
    y-axis "Detector accuracy" 0.50 --> 0.85
    bar [0.586, 0.819]

These points are from the same experiment and are therefore much more interpretable than juxtaposing unrelated steganalysis studies. They show the commonly observed direction of the tradeoff, not a universal law. source

Prompt-controlled LLM steganography. With an instruction-following LLM, the “codebook” can be stated in natural language: one stylistic or semantic behavior represents one symbol and another behavior represents another. Roger and Greenblatt explicitly tested prompt-only schemes that did not require logit access, including asking LLMs to encode messages in their responses and subsequently asking another model to recover them. source

A generic form is:

PROMPT-CONTROLLED-ENCODE(task, message_chunk, codebook):
    prompt ← task
    prompt += "Answer normally, while satisfying carrier behavior"
    prompt += codebook[message_chunk]

    answer ← LLM(prompt)

    if quality_check(answer, task) fails:
        regenerate or mark erasure

    return answer

PROMPT-CONTROLLED-DECODE(answer, codebook):
    features ← classify_carrier_behaviors(answer)
    return inverse_codebook(features)

This is attractive because it works through black-box APIs and can encode in vocabulary, syntax, tone, ordering, examples, or reasoning structure. It is less deterministic than arithmetic coding, however, and ordinary paraphrasing often destroys surface manifestations. Roger and Greenblatt's experiments found that paraphrasing almost always reduced remaining information below two bits/answer in their tested schemes. source

Semantic and embedding-space channels. Bai et al.'s 2024 semantic steganography framework explicitly moves beyond symbolic token coding: it builds a semantic space using ontology–entity trees, maps secret messages to regions of that space, and asks an LLM to generate text corresponding to the desired semantic region. Their method combines semantic mapping with feedback/rejection sampling and arithmetic coding. source

A simplified abstraction is:

SEMANTIC-ENCODE(task, message, key):
    z ← map_bits_to_semantic_region(message, key)

    repeat:
        text ← LLM.generate(task, semantic_constraint=z)
        representation ← semantic_encoder(text)

    until representation lies safely inside z
          and task_quality(text) is acceptable

    return text

SEMANTIC-DECODE(text, key):
    representation ← semantic_encoder(text)
    z_hat ← identify_keyed_semantic_region(representation)
    return region_to_bits(z_hat, key)

Dense embeddings can play a closely related role even when the application is watermarking rather than arbitrary-message steganography. POSTMARK, for example, computes a semantic embedding of text, selects semantically associated watermark words from an embedding-indexed table, and asks a separate instruction-following model to rewrite the passage so those words appear naturally. The detector recomputes the semantic word set and counts matches. Because POSTMARK is a watermark rather than a general arbitrary-payload channel, its capacity should not be compared directly with secret-message systems, but the architecture demonstrates how embedding space can define a context-dependent lexical codebook. source

Capacity, naturalness, recovery, and achievable rates#

For an ideal distribution-preserving encoder, the amount of hidden information available in a choice is constrained by its entropy:

\[
H(X)=-\sum_xp(x)\log_2p(x).
\]

A binary choice having probabilities \(0.5/0.5\) has one bit of entropy; a \(0.9/0.1\) choice has only about 0.469 bits. Arithmetic-coding steganography tries to use that probabilistic entropy efficiently rather than demanding an integer number of bits from every position. Ziegler et al.'s arithmetic-coding construction and Shen et al.'s SAAC are direct embodiments of this information-theoretic idea. source

For traditional lexical methods, observed capacity is dramatically below the grammatical entropy of English because very few positions are safely modifiable. Chang and Clark's review reports roughly 0.67 bits/sentence for earlier lexical-substitution systems; their own context-checked system achieved roughly two information carriers per sentence, each guaranteed to carry at least one bit. T-Lex's small dictionary yielded approximately 0.1 bits/sentence. source

Neural generation makes every generation step a potential carrier. Ueoka et al. summarize generation-based capacities in the range of 1–5 bits/word; in their own comparison, the GPT-2 system carried 1.67 bits/word versus 0.204 for masked-LM editing. At 20 words/sentence, 1.67 bits/word would correspond to roughly 33 bits/sentence, but that conversion is only illustrative: sentence length, tokenizer boundaries, stop conditions, and text genre all alter the number. source

Noise and recoverability. Suppose contextual substitutions behave as an independent binary symmetric channel with bit error probability \(e\). Its Shannon capacity per usable carrier is

\[
C_{\rm BSC}=1-H_2(e),
\]

with

\[
H_2(e)=-e\log_2e-(1-e)\log_2(1-e).
\]

If only fraction \(q\) of words are usable and an independent fraction \(\delta\) of carriers are erased by editing, a useful first-order model is

\[
R_{\rm achievable}
\lesssim
q(1-\delta)\,[1-H_2(e)]
\quad\text{bits/word}.
\]

For an illustrative 20-word sentence with \(q=0.10\), \(e=0.02\), and \(\delta=0.05\),

\[
R\approx 0.0816\text{ bits/word}
\]

or about

\[
1.63\text{ reliable bits/sentence}.
\]

This is an analytical example, not a published experimental result.

The implication for error correction is straightforward: an encoder operating at the raw two bits/sentence in that example has no redundancy and cannot approach arbitrarily low decoding error. A practical system needs to operate below channel capacity, reserving symbols for forward error correction and synchronization. Repetition codes are simple but inefficient; BCH, Reed–Solomon, convolutional, or LDPC-style coding can provide stronger protection depending on whether errors occur as isolated bit flips, erasures, or bursts. The steganographic complication is that redundancy itself consumes scarce carrier opportunities.

The real channel is also rarely memoryless. A paraphraser may erase an entire sentence's lexical channel; a deletion may shift every subsequent carrier boundary; a tokenizer disagreement may cause a burst of decoder failures; a semantic rewrite can change several correlated choices at once. Ueoka et al. found in one configuration that 1.41% of masked tokens had substitution candidates that did not reproduce the original subword segmentation, directly illustrating a synchronization hazard. source

For that reason a robust receiver architecture typically needs conceptual equivalents of

\[
\text{frame marker}\;||\;\text{sequence index}\;||\;\text{ECC(payload)}\;||\;\text{integrity check}.
\]

Yet explicit synchronization patterns can themselves become steganalytic features. The optimal design therefore trades receiver reliability against observable structure rather than maximizing either independently.

Naturalness. Perplexity is commonly reported for generation-based systems:

\[
\operatorname{PPL}(x_{1:N})
=
\exp\left[
-\frac1N\sum_{t=1}^{N}
\ln P_\theta(x_t\mid x_{<t})
\right].
\]

Low perplexity means the evaluation LM assigned high probability to the text, but it is not equivalent to human naturalness, semantic fidelity, factual correctness, or indistinguishability. Contemporary watermarking research explicitly notes the limits of perplexity as a standalone quality measure and supplements it with human and task-specific evaluations. source

Human evaluation provides more interpretable evidence. Chang and Clark's contextual synonym sentences averaged 3.33/4 versus 3.67/4 for originals and 2.82/4 for randomly substituted controls; all three differences were significant at \(p<0.01\) under their Wilcoxon signed-rank analysis. source

Ueoka et al.'s masked-BERT stegotext scored \(4.32\pm0.97\) on a five-point scale, GPT-2 stegotext \(4.43\pm0.89\), and real text \(4.54\pm0.78\). Thus the edit-based system was substantially harder for their automatic discriminator than GPT-2 generation even though humans rated GPT-2 slightly higher—a concrete demonstration that human and statistical naturalness need not coincide. source

Shen et al. report that 51% of their SAAC-generated cover texts fooled human eavesdroppers. Ziegler et al. similarly observed strong human plausibility at moderate rates, especially for arithmetic coding; in their experiments, low-rate arithmetic-coded generations approached human-written baselines in the specific sentence-level evaluation. source

A rigorous evaluation should therefore report at least four distinct quantities:

\[
\text{Payload rate},\quad
\text{receiver BER/message error},\quad
\text{human acceptability},\quad
\text{machine detection}.
\]

Collapsing them into “quality” obscures precisely the tradeoffs that determine whether a method is actually useful.

Detection, steganalysis, and adversarial robustness#

The steganalyst observes \(x\) and tests

\[
H_0:x\sim P_C
\qquad\text{versus}\qquad
H_1:x\sim P_S.
\]

For known distributions, the optimal Neyman–Pearson statistic is a likelihood ratio,

\[
\Lambda(x)=\frac{P_S(x)}{P_C(x)},
\]

with a detection threshold selected for the desired false-positive rate. Cachin explicitly casts passive steganalysis as this kind of hypothesis-testing problem and uses relative entropy to quantify the difference between cover and stego distributions. source

A natural measure is

\[
D_{\mathrm{KL}}(P_S\Vert P_C)
=
\sum_xP_S(x)\log\frac{P_S(x)}{P_C(x)}.
\]

At equal priors, the optimal single-sample classification accuracy is tied to total-variation distance:

\[
A^*
=
\frac12\left(1+\operatorname{TV}(P_C,P_S)\right).
\]

Pinsker's inequality gives, using natural logarithms,

\[
\operatorname{TV}(P_S,P_C)
\le
\sqrt{\frac12D_{\mathrm{KL}}(P_S\Vert P_C)}.
\]

Consequently, a small KL divergence bounds the advantage of any ideal one-sample detector. This is why KL-based imperceptibility is a meaningful objective in SAAC and related distribution-preserving schemes, although finite-sample estimates of KL can themselves be unreliable in enormous text spaces. Cachin's framework supplies the foundational interpretation, while Shen et al. empirically use a KL metric alongside payload. source

Synonym-frequency analysis. The naïve binary scheme leaves a particularly obvious signature. For a synonym family with expected counts \(E_i=np_i\) and observed counts \(O_i\), one can compute

\[
\chi^2=\sum_i\frac{(O_i-E_i)^2}{E_i}.
\]

Repeatedly forcing naturally skewed alternatives toward equal use moves this statistic away from its cover distribution. A detector need not know the hidden bits; it only needs a sufficiently accurate model of ordinary contextual synonym frequencies.

The scale of the resulting sample-size effect can be quantified. Consider a binary synonym whose genuine contextual rate is \(p_0=0.50\) but steganographic use changes it to \(p_1=0.55\). Under an approximate two-sided level-\(0.05\) proportion test, detection power is about 17% after 100 observations, 29% after 200, 61% after 500, 89% after 1,000, and 99% after 2,000. These figures are normal-approximation calculations, not measurements from a particular stegosystem. They demonstrate why tiny lexical biases that are invisible in a paragraph can become conspicuous across a user's long-term corpus.

That theoretical phenomenon is visible empirically in Wilson et al.'s Twitter study. One-bit automatic CoverTweet had AUC 0.551 for an individual tweet, essentially weak detection, but AUC rose to 0.9631 when evidence from 100 tweets was pooled. Individual human-filtered CoverTweet had AUC 0.509, virtually chance, yet even manually filtered material became detectable when enough samples were combined. source

xychart-beta
    title "Pooling weak lexical evidence can make detection strong"
    x-axis ["1 tweet", "100 tweets"]
    y-axis "AUC, automatic CoverTweet" 0.50 --> 1.00
    bar [0.551, 0.9631]

Wilson et al. also showed how warden knowledge changes detection. For batches of ten, a rich feature combination yielded error rate 0.169 against two-bit automatic CoverTweet and 0.168 against one-bit T-Lex. PPDB-derived paraphrase features were especially effective against CoverTweet, while n-gram features were stronger against T-Lex because T-Lex did not explicitly minimize language-model distortion. source

Useful steganalytic features therefore include contextual n-gram probabilities, synonym-family frequencies, unusual word-rank distributions, paraphrase-database compatibility, word/character lengths, likelihood under one or more language models, perplexity residuals, semantic consistency, and features specifically reverse-engineered from the suspected encoder. Wilson et al. found that even a paraphrase resource different from the exact source available to the steganographer could add detection value, indicating that perfect knowledge of the encoder's dictionary is not always required. source

Language-model detectors. A detector can compute a score such as

\[
S_{\rm NLL}(x)
=
-\frac1N\sum_t\log P_\phi(x_t\mid x_{<t}),
\]

or use token-level ranks, entropy, likelihood curvature, or embeddings as classifier features. For synonym systems, a more targeted statistic compares the observed alternative with conditional probabilities of all members of its synonym set. If the encoder overuses low-probability choices to satisfy payload bits, the accumulated log-likelihood ratio becomes evidence for \(H_1\).

Crucially, a steganographic encoder may explicitly optimize against one such model. CoverTweet already used a language-model-based distortion criterion, which weakened some n-gram attacks relative to T-Lex. This is an early example of an arms race that is even more important with LLM generators: evaluation under a single detector risks measuring adaptation to that detector rather than genuine indistinguishability. source

Finite-precision attacks. Distribution-preserving arithmetic coding deserves particular caution. Its security argument assumes ideal probability arithmetic. Cao, Wang, and Hu's 2026 “Low-Probability Vanishing” work attacks the numerical implementation rather than semantic quality: in their experiments their RRNs-HT method averaged 86.95% detection accuracy against arithmetic-coded steganography and 77.40% against Meteor, whereas five semantic steganalysis baselines remained near 50% on the tested datasets. For FP16 arithmetic coding they report statistically detectable effects with relatively short sequences in some settings. source

This matters conceptually: a proof that

\[
P_S=P_{\rm LM}
\]

for an ideal mathematical algorithm does not show that

\[
P_{\rm implementation}=P_{\rm LM}
\]

after floating-point rounding, top-\(k\) pruning, tokenizer conversion, API changes, or nondeterministic kernels.

Paraphrasing as an active defense. Surface synonym coding is especially fragile because its signal resides in how an idea is worded. A competent paraphraser preserving meaning has no reason to preserve the same word choice. Roger and Greenblatt found that their paraphrasing defenses almost always reduced the surviving covert capacity below two bits/answer and concluded that, under their studied conditions, more than roughly three bits/kB was difficult to retain without conspicuous degradation. source

That should not be generalized to semantic channels. The 2026 conceptual-steganography work encodes bits in higher-level reasoning strategies and finds markedly lower post-paraphrase bit-error rates than a keyword carrier, while pre-paraphrase concept decoding exceeded 95.5% message accuracy with bit error at most 1.3% in its reported noise-floor experiments. The authors' interpretation is that meaning-preserving paraphrasers tend to preserve high-level reasoning behavior even while replacing words. source

A semantic-space approach similarly aims to make the secret depend on entities or meanings that survive lexical rewriting. Bai et al. explicitly motivate their method by the vulnerability of symbolic token-level coding to real communication channels and report robustness against attacks that preserve or ignore surface semantics, although the work should be treated as an emerging research result rather than settled evidence. source

The resulting robustness hierarchy is roughly:

\[
\text{exact word choice}
<
\text{syntax/style}
<
\text{paraphrase-level structure}
<
\text{semantic/conceptual content}
\]

under ordinary meaning-preserving paraphrasing, but the ordering reverses in other threat models. A defender allowed to regenerate an answer from the underlying task rather than preserve the original semantics can erase semantic carriers too. Roger and Greenblatt explicitly distinguish ordinary paraphrasing from context-aware regeneration for this reason. source

Recommended experimental program, limitations, and ethics#

A useful new study should not ask merely “how many bits can we hide?” It should estimate a capacity–quality–detectability–robustness surface under an explicit adversary.

The core experiment should compare at least five families under the same text distribution: fixed synonym pairs; context-filtered synonyms; masked-LM substitutions; probability-matched autoregressive token coding; and black-box LLM paraphrase/semantic selection. This directly addresses a weakness of the literature: published payload and detector numbers frequently come from incomparable datasets and threat models. Wilson et al., Chang and Clark, Ueoka et al., and neural-generation papers each evaluate materially different channels. source

For natural-language data, a sound corpus mix can reuse public benchmarks already represented in this literature—for example news/web corpora for conventional text, Twitter-like material for short messages, AlpacaEval-like instruction responses, and AQUA-RAT or comparable reasoning tasks for LLM answers. Roger and Greenblatt use AlpacaEval and AQUA-RAT for capacity-versus-task-performance analysis; Ueoka et al. explicitly encountered domain-mismatch effects when their discriminator and text source differed, which makes cross-domain testing essential rather than optional. source

Capacity procedure. Measure both gross payload

\[
R_g=\frac{\text{embedded message bits}}{\text{output words}}
\]

and successfully recovered payload

\[
R_n
=
\frac{I(M;\hat M)}{\text{output words}},
\]

where \(I(M;\hat M)\) is mutual information. Gross bits overstate useful capacity whenever decoding errors occur. Roger and Greenblatt explicitly frame effective steganographic capacity through mutual information and explore approximations based on perfect-message recovery and per-bit errors. source

For an \(n\)-bit message passed through independent binary errors \(e_i\), a convenient approximation is

\[
C
=
\sum_{i=1}^{n}\left[1-H_2(e_i)\right].
\]

For correlated errors, estimate \(I(M;\hat M)\) directly from a large randomized message set or fit an explicit channel model rather than treating bit errors as independent. Roger and Greenblatt show that different error assumptions can materially change estimated capacity, providing a useful warning against reporting only exact-recovery percentage. source

Detectability procedure. Detectors should be divided into three knowledge levels. A black-box warden knows only the language/domain; a gray-box warden knows the algorithm family but not the key; a white-box warden knows the encoder and model but not the secret payload/key. Evaluating only the first makes weak lexical schemes look stronger than they are; Wilson et al.'s results show how encoder-specific paraphrase features can sharply improve detection. source

For each payload \(R\), estimate

\[
\operatorname{AUC}(R),\qquad
\operatorname{TPR}_{\mathrm{FPR}=10^{-2}}(R),\qquad
\operatorname{TPR}_{\mathrm{FPR}=10^{-3}}(R).
\]

Then repeat after pooling \(k=1,5,10,50,100\) samples from a common sender. The difference between Wilson et al.'s AUC 0.551 at one automatic CoverTweet and 0.9631 at 100 tweets demonstrates why this longitudinal experiment is indispensable. source

A capacity–detectability frontier should be reported rather than one operating point:

\[
\mathcal F
=
\left\{
(R,D):
\text{no tested configuration has both higher }R
\text{ and lower }D
\right\},
\]

where \(D\) could be AUC advantage above 0.5 or TPR at a fixed false-positive rate. Naturalness can be imposed as a constraint, for example

\[
\text{human preference loss}\le 5\%.
\]

That provides a scientifically meaningful answer to “how much hidden information is achievable while remaining acceptably natural and difficult to detect?”

Reliability experiment. The receiver should be tested under both identical and deliberately mismatched software environments: different tokenizer patch versions, FP16 versus FP32, slightly different LM checkpoints, whitespace normalization, Unicode normalization, sentence segmentation, and API-generation versions. Ueoka et al.'s segmentation observation and the 2026 finite-precision attack imply that these apparently low-level implementation choices can affect both extraction and security. source

Human-study design. Use balanced randomized presentation with annotators blinded to method and payload. Measure naturalness separately from detection: “Is this sentence well written?” and “Do you think this contains a hidden code?” are not equivalent judgments. Chang and Clark intentionally evaluated linguistic quality rather than merely asking whether a change was noticed; Ueoka et al. similarly distinguish human ratings from automatic steganalysis. source

Statistical reporting should include confidence intervals and predeclared tests. For forced-choice detection, test against the 50% null with binomial confidence intervals. For Likert naturalness, report distributions and a suitable paired or ordinal analysis in addition to means. For ROC results, bootstrap documents or, for longitudinal experiments, users rather than individual messages, because messages from the same author are dependent.

Several limitations apply to essentially all published capacity figures. “Word” may mean whitespace-delimited word, subword token, or model token. Real sentences vary greatly in length. Candidate sets are domain- and context-dependent. A model's perplexity is relative to that model, not a universal probability of English. Human evaluations are usually small compared with the enormous space of possible texts. Detectors can overfit generator artifacts. Conversely, an encoder can overfit the detector used during development. Results from one English-language domain should not be assumed to transfer to morphologically richer languages. The literature itself repeatedly exhibits these quality/payload, domain-mismatch, and model-specific effects. source

There is also a fundamental epistemic limitation: failure to detect is not evidence of perfect secrecy. AUC near 0.5 means only that a particular detector on a particular finite dataset found little usable signal. Wilson et al.'s pooled attack and Cao et al.'s numerical-artifact detector are striking examples of schemes appearing secure under one observation model and becoming detectable after the adversary changes its statistic or accumulates more evidence. source

Finally, linguistic steganography is inherently dual use. It has legitimate applications in watermarking, provenance, censorship resistance, covert authentication, and research into communication privacy; it can also conceal exfiltration, coordinated model behavior, or malicious communication. Ueoka et al. explicitly describe this dual-use tension, noting both censorship-resistance motivations and malicious-data risks. Modern LLM work makes the issue particularly salient because a model can potentially learn or be trained to communicate information through outputs not recognized by ordinary oversight. source

For research publication, a defensible practice is to release evaluation corpora, detectors, aggregate codebook-generation procedures, and robustness tests while treating deployment-ready high-capacity covert exfiltration systems with greater caution. More important scientifically, every paper should state the intended warden's knowledge, whether the secret key is assumed compromised, whether multiple messages can be pooled, what transformations the channel permits, and whether “security” means human indistinguishability, low detector AUC, bounded KL divergence, or formal computational indistinguishability. Cachin and Hopper et al. make clear that these are distinct security notions. source

Primary sources and links#

The following are the most useful primary or official research sources for reproducing or extending the analysis.

Taken together, these sources show a remarkably consistent progression: the primitive “synonym A versus synonym B” channel remains a useful model for understanding linguistic steganography, but modern systems increasingly treat all naturally available linguistic entropy—lexical, syntactic, probabilistic, semantic, and conceptual—as potential carrier space. The decisive question is no longer whether information can be hidden in natural word choice; it demonstrably can. The research frontier is how close the resulting distribution can remain to genuinely innocent language under repeated observation, realistic transformations, implementation imperfections, and an adaptive adversary. source