# Hidden Information in Natural Language 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. citeturn17view7turn17view6turn19view5 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. citeturn19view4turn19view5turn19view6 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. citeturn15view0turn18view0turn18view3 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. citeturn19view0turn19view1turn18view4turn18view5 “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. citeturn15view3turn15view6turn20search13 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. citeturn17view0turn17view1 The empirical literature strongly suggests the following ordering: | Approach | Typical / reported payload | Human naturalness | Detectability | Implementation | Shared secret / shared state | |---|---:|---|---|---|---| | Null/acrostic-style positional channel | Usually very low per word | Potentially excellent | Often easy if rule suspected | Low | Extraction rule | | Fixed synonym pairs / T-Lex | ~0.1 bits/sentence for T-Lex | Context dependent | Detectable statistically in aggregate | Low–medium | Dictionary + bit assignment | | Context-filtered synonym substitution | ~0.67–2 bits/sentence in published systems | Good with strong filtering | Low per sample; frequency/context artifacts remain | Medium–high | Synonym graph/coding rule; optionally key | | Sentence/paraphrase selection | Up to 1 bit/sentence in Chang–Clark's proposed construction | Potentially high | Depends strongly on paraphrase generator | High | Paraphrase/codebook rule | | Masked-LM editing | 0.204 bits/word in one BERT configuration | 4.32/5 vs. 4.54/5 real text | 58.6% detector accuracy in that experiment | Medium | Model, masking strategy, encoding strategy | | Neural token generation | Often ~1–5 bits/word | Often strong at moderate payload | Can become high at larger payload; implementation leakage matters | High | Exact LM/coder; usually key/seed | | Prompt-controlled LLM channel | Several bits/answer feasible in tested schemes | Often very high | Surface variants vulnerable to paraphrase | Low–medium | Prompt/codebook | | Semantic / conceptual channel | Method-dependent; potentially substantially larger semantic symbols | Potentially high | Harder for lexical detectors | High | Semantic codebook/model/key | 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. citeturn19view4turn19view5turn15view4turn18view0turn19view0 ## 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. citeturn17view0turn17view1 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. citeturn17view0turn17view1 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. citeturn19view5 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. citeturn18view3turn17view0 ## 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. citeturn3search1turn16search0 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. citeturn21search6turn21search12 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. citeturn17view6turn17view7 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. citeturn4search0turn4search11turn20search7 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. citeturn18view3turn17view2turn15view0turn20search3turn18view4 ```mermaid 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. citeturn17view6turn17view7turn19view5turn18view3turn15view0turn17view2turn19view0turn20search3turn18view4turn20search13 ## 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. citeturn19view7turn20search7 A keyed generic construction can be represented as: ```text 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. citeturn20search7turn15view1 **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. citeturn19view7 ```text 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_{ 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. citeturn15view4 **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. citeturn19view3 A generic form is: ```text 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. citeturn19view1 **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. citeturn20search0turn20search3 A simplified abstraction is: ```text 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. citeturn17view5 ## 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. citeturn7view0turn18view3 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. citeturn19view4turn19view5 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. citeturn15view0turn15view4 **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. citeturn15view1 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_{