The Encoding of Covert Information Through Lexical Substitution and Generative Models

The Evolution and Taxonomy of Steganography#

In the broader discipline of information security, the protection of data in transit is traditionally delegated to cryptography, which algorithmically scrambles the contents of a message to render it incomprehensible to unauthorized interceptors. However, the transmission of heavily encrypted ciphertext inherently alerts monitors to the presence of sensitive communications, a vulnerability in environments where the mere act of encrypted communication is prohibited or highly scrutinized. Steganography, derived from the Greek words steganos (covered or concealed) and graphia (writing), circumvents this vulnerability by hiding the very existence of the message1. In information theory, a steganographic system establishes a covert, parasitic communications channel hidden within the medium of a legitimate, seemingly innocent communication channel3. The origins of steganography date back to antiquity. The ancient Greek historian Herodotus documented instances where secret messages were tattooed on the shaved heads of trusted slaves, concealed once their hair regrew, or etched into wooden tablets before being covered with innocuous wax1. Throughout the Renaissance, Johannes Trithemius advanced the field significantly with his treatises Polygraphia and Steganographia (1499), which disguised cryptographic and steganographic principles as texts on magic1. During the World Wars, female spies utilized subtle variations in knitting patterns—such as an irregular stitch or an intentional hole—to encode messages, while others relied on invisible inks, acrostics, and musical notation, as employed historically by figures like J.S. Bach and John Wilkins1. Mathematical formalization of steganography divides systems into three primary architectural paradigms: pure steganography, shared-secret steganography, and public-key steganography4. A pure steganographic system operates without prior exchange of keys, defined as a tuple [embedded figure or formula in source report], where [embedded figure or formula in source report] represents the set of cover objects, [embedded figure or formula in source report] the set of messages, [embedded figure or formula in source report] the embedding function that maps [embedded figure or formula in source report], and [embedded figure or formula in source report] the extraction function4. Shared-secret systems introduce a pre-shared key [embedded figure or formula in source report] to govern the embedding and extraction pathways, while public-key systems leverage asymmetric cryptography, ensuring that even if the embedding protocol is known, extraction remains impossible without the private key4. Modern digital steganography typically targets highly redundant media, such as high-resolution images, audio files, and video streams, where subtle manipulations of least significant bits are imperceptible to human senses1. Linguistic steganography, which focuses on natural language text as the cover medium, presents a significantly more formidable challenge3. Unlike the dense pixel arrays of digital images, natural language possesses minimal structural redundancy; a single incorrect word modification can introduce glaring syntactical errors, semantic absurdities, or stylistic anomalies that immediately alert human readers or automated steganalysis tools6. Linguistic steganography is traditionally bifurcated into two models: injective (or modification-based) and generative1. Injective methods take an existing cover text and apply systematic, imperceptible modifications—such as synonym substitution, syntactic restructuring, or adjective deletion—to encode the secret payload11. Generative steganography, conversely, relies on linguistic algorithms or Large Language Models (LLMs) to synthesize an entirely new text directly conditioned on the secret message, a technique often termed "coverless steganography"14. This report provides an exhaustive analysis of lexical substitution steganography, exploring its early theoretical frameworks, the paradigm shift toward LLM-based generative methods, the mathematical limits of information capacity, the critical requirement of system reliability, and the advanced statistical steganalysis techniques designed to detect these covert channels.

The Mechanics of Lexical Substitution#

Lexical steganography via synonym substitution is a symbolic and semantic approach to data embedding. The foundational premise relies on the linguistic phenomenon of synonymy—the existence of distinct words within a language that share equivalent semantic meanings6. By replacing a word with an equivalent synonym, a sender can encode binary data without altering the overarching meaning, syntactic structure, or stylistic tone of the sentence6. At its core, a synonym substitution system requires the establishment of a "synset" (synonym set). If a specific word in a cover text belongs to a predefined synset containing [embedded figure or formula in source report] acceptable synonyms, the choice among these synonyms can seamlessly encode exactly [embedded figure or formula in source report] bits of secret information. For instance, if a synset for the concept of a large urban area comprises the words {city, metropolis}, substituting the original word with "city" might represent a binary 0, whereas replacing it with "metropolis" represents a binary 112. By sequentially iterating through a document and making these substitutions in accordance with a pre-encrypted binary message, the sender transforms the natural cover text into a stego-text capable of transporting a hidden payload across monitored networks9. However, the practical application of this theoretical model encounters severe linguistic friction. Natural language is intrinsically contextual, and words frequently exhibit polysemy, meaning they possess multiple senses depending on their surrounding syntax and semantic context. A rigid algorithmic substitution of the word "too" with its synonym "also" might function flawlessly in the sentence "I want to go, too," but substituting it in the phrase "the bed is too big" yields "the bed is also big," destroying the original semantic intent17. Furthermore, substituting synonyms indiscriminately can violate authorial style or historical appropriateness; replacing "nothing" with "nada" in a 19th-century English novel produces a glaring stylistic anomaly12. Therefore, the successful implementation of synonym substitution requires rigorous linguistic databases—most notably Princeton’s WordNet—and sophisticated Word Sense Disambiguation (WSD) protocols to ensure that lexical swaps remain genuinely imperceptible to both human wardens and automated steganalyzers17.

Early Computational Frameworks and Synonym Hashing#

Prior to the integration of deep learning and probabilistic neural networks, linguistic steganography relied heavily on deterministic rulesets, static lexical databases, and complex mathematical encoding algorithms. These early computational systems were defined by their struggle to balance high embedding capacity with the preservation of natural linguistic flow.

Tyrannosaurus Lex (T-Lex) and Mixed-Base Mathematics#

In 1999, Keith Winstein developed Tyrannosaurus Lex (T-Lex), a pioneering and highly influential implementation of computational lexical steganography that served as the baseline for subsequent research20. Recognizing the computational bottlenecks of real-time Word Sense Disambiguation, T-Lex utilized WordNet to pre-compile a database of approximately 20,000 words grouped into strict "interchangeability sets"17. To ensure that words were safe to swap without breaking the sentence's meaning, T-Lex enforced rigorous substitution constraints: words with a single defined sense that shared a synset were deemed unconditionally interchangeable. For words with multiple senses, substitution was only authorized if the candidate words shared identical synonym sets across all their possible senses—an operation defined mathematically as the intersection of their sense sets17. A fundamental limitation of a naïve synonym substitution algorithm is the requirement that synset sizes must perfectly equal a power of two ([embedded figure or formula in source report]) to map to binary bits. A synset containing exactly three valid synonyms presents an informational inefficiency, as it can encode one bit ([embedded figure or formula in source report]) while wasting the remaining capacity, or it risks undefined behavior if asked to encode two bits ([embedded figure or formula in source report]). To exploit the maximum informational capacity of the English language, T-Lex introduced an "Ideal Coding" mechanism utilizing mixed-base mathematics17. Under the ideal coding framework, a sequence of replaceable words in a document is treated as a single, massive mixed-base integer. If a document features three consecutive words belonging to synsets of sizes 3, 5, and 3, respectively, the algorithm treats this sequence as a state space capable of representing [embedded figure or formula in source report] unique states. This capacity is sufficient to encode [embedded figure or formula in source report] bits of secret data. The binary message is mapped directly to a specific integer state, dictating the exact permutation of synonyms chosen across the entire multi-word block17. To prevent this ideal coding algorithm from attempting to process computationally impossible integers over long documents (e.g., numbers exceeding [embedded figure or formula in source report]), T-Lex segmented documents into smaller, manageable blocks. Within these blocks, it introduced an adaptive "Word Choice Hash"17. Because the representational capacity of a text block typically exceeded the exact bit payload assigned to it due to oversampling, multiple different synonym configurations could mathematically hash to the same binary payload. The T-Lex encoder calculated these various permutations and deliberately selected the specific synonym configuration that required the fewest total word modifications relative to the original text. By adapting the modulation frequency based on the payload size, T-Lex minimized grammatical disruption and statistical distortion17. Despite its mathematical elegance, T-Lex was fundamentally flawed by its reliance on static databases and its blindness to localized context. The system frequently generated syntactically awkward phrasing, rendering it highly susceptible to both human suspicion and basic statistical steganalysis12.

Bolshakov’s Transitive Closure and Decoding Ambiguity#

In 2004, researcher Igor Bolshakov identified a critical structural flaw in lexical substitution: decoding ambiguity caused by overlapping synsets24. If the word "shame" belongs to one synset containing {pity, shame} and a secondary synset containing {shame, disgrace, ignominy}, a steganographic sender might replace "shame" with "disgrace" to encode a bit3. However, when the receiver (Bob) encounters the word "disgrace," he has no deterministic way to know which original synset Alice utilized to encode the data. If Bob evaluates the wrong synset, the extracted binary sequence is corrupted. Bolshakov proposed resolving this ambiguity by applying the mathematical principle of transitive closure to overlapping synsets. Under this method, any synsets that share a common word are forcefully merged into a single, comprehensive "super-synset"24. While this elegant mathematical solution completely eliminated decoding ambiguity, it introduced severe linguistic degradation. Applying transitive closure to a dense lexical network like WordNet creates massively bloated synsets containing words with drastically divergent contextual meanings, forcing the algorithm to make inappropriate substitutions that destroy the semantic integrity of the stego-text24.

Contextual Fitness and Vertex Color Coding#

To resolve the dual challenges of contextual inaccuracy and extraction ambiguity without relying on transitive closure, researchers Ching-Yun Chang and Stephen Clark (2010, 2014\) proposed a framework that integrated statistical corpus analysis with advanced graph theory3. To guarantee semantic naturalness, Chang and Clark abandoned rigid, pre-compiled interchangeability rules. Instead, they dynamically evaluated substitution candidates using the massive Google n-gram corpus, a methodology they validated against human-annotated data from the SemEval-2007 lexical substitution task3. By calculating the relative frequency of a proposed synonym within its precise surrounding [embedded figure or formula in source report]\-gram context, their system quantitatively assessed "context fitness." Any proposed synonym that fell below a specific contextual probability threshold was deemed unacceptable and rejected, ensuring that the resulting stego-text remained syntactically and semantically fluid3. To address the decoding ambiguity problem, Chang and Clark introduced a novel Vertex Coding algorithm3. They modeled the text's viable substitution options as an undirected graph, where the vertices (nodes) represented acceptable synonyms, and the edges linked words that were synonymous with one another3. The algorithmic objective was to assign unique binary codewords (e.g., 00, 01, 10, 11\) to each vertex such that no ambiguity could arise during extraction, all without deleting the vast numbers of valid synonyms that transitive closure would otherwise corrupt3. The Vertex Coding algorithm utilized a sophisticated dual-priority queuing system:

1. Queue 1 ([embedded figure or formula in source report]): Vertices possessing three or more neighbor edges were prioritized. Because a vertex with three interconnected neighbors mathematically restricts those neighbors from sharing its assigned codeword, these heavily connected, highly restrictive nodes had to be resolved first to prevent algorithmic deadlocks. 2. Queue 2 ([embedded figure or formula in source report]): All remaining nodes were sorted to prioritize vertices with exactly two neighbors.

As the algorithm iterated through the concatenated queue, it accessed a cannot\_access array for each node—a list of restricted codewords that the node was forbidden from using due to adjacent assignments3. The algorithm randomly selected an available codeword for the target vertex, assigned it, and immediately deleted that specific codeword from the cannot\_access arrays of all adjacent neighboring vertices3. Following the initial coding, post-processing steps of codeword reduction and error correction were applied to minimize redundancy and resolve lingering graph conflicts3. This dynamic graph-coloring technique guaranteed that regardless of which synonym was ultimately chosen for substitution, the receiver could unambiguously decode the associated bits by reconstructing the graph. Furthermore, the system exhibited high robustness in adherence to Kerckhoffs's principle2. Because the randomizer seed used in the vertex coding function and the specific probability threshold used in the n-gram evaluation functioned as a shared cryptographic key between Alice and Bob, an adversarial warden (Eve) could possess the full algorithm but remain mathematically unable to reconstruct the coded synonym graph without the key2.

The Generative Paradigm: Large Language Models and Provable Security#

The rapid proliferation and evolution of neural network architectures, specifically autoregressive Large Language Models (LLMs) based on the generative pre-trained transformer (GPT) architecture, precipitated a fundamental paradigm shift in linguistic steganography11. Rather than injecting secrets by modifying an existing cover text—which invariably leaves traces of statistical distortion and word-frequency flattening—modern methods employ generative text steganography (or coverless steganography)11. In this framework, the LLM is leveraged to generate a wholly new, contextually fluent text from scratch, actively conditioning the sampling of its output on the secret message15. At each time step [embedded figure or formula in source report], an autoregressive LLM outputs a conditional probability distribution [embedded figure or formula in source report] over its entire vocabulary of tokens15. Steganographic algorithms intercept and manipulate this sampling process, utilizing the secret binary data to dictate which token is selected, thereby encoding the payload directly into the semantic fabric of the generated text.

Entropy Coding: Arithmetic and Huffman Implementations#

The earliest generative LLM approaches sought to map the secret binary string directly to the language model's output distribution by running standard data compression algorithms in reverse. Arithmetic Coding (AC), originally engineered by Witten et al. (1987) for optimal, loss-less data compression, maps a finite-length text sequence to a precise mathematical interval within the real number range [embedded figure or formula in source report]14. In the context of LLM steganography, AC is inverted to function as a decoder. The pre-encrypted secret message acts as a uniform random number situated in [embedded figure or formula in source report]. At each generation step, the AC algorithm recursively partitions the [embedded figure or formula in source report] interval based on the exact probabilities of the LLM's predicted tokens. The algorithm selects the specific token whose cumulative probability interval encapsulates the secret random number14. Because AC dynamically adjusts the embedding rate based on the fluctuating entropy of the LLM's probability distribution, it enables a highly efficient, variable-length coding scheme that naturally matches the statistical peaks and valleys of language generation15. Similarly, Huffman Coding (HC) constructs a dynamic, full binary tree based on the token probabilities predicted at each time step14. Tokens with high probabilities are assigned shorter binary paths near the root of the tree, while less likely tokens receive longer paths extending to the leaves. A segment of the secret bitstream is used to navigate the tree from root to leaf, thereby selecting the terminal token for generation14. Advanced iterations, such as the Patient-Huffman algorithm, evaluate the Kullback-Leibler Divergence (KLD) between the original, untampered LLM distribution and the steganographically altered token distribution15. If embedding a specific bit forces the selection of a highly improbable token—thereby spiking the KLD and generating a statistically suspicious word—the algorithm exhibits "patience." It defaults to standard sampling for that step, deferring the secret embedding to a subsequent token where the distribution possesses higher natural entropy15.

Provably Secure Steganography: Adaptive Dynamic Grouping (ADG)#

While Arithmetic and Huffman coding significantly increased payload capacity, they invariably skewed the sampling distribution away from the LLM’s true baseline. These minute statistical footprints are exploitable by advanced steganalysis tools31. This vulnerability sparked the pursuit of Provably Secure Steganography (PSS), a theoretical framework pioneered by Cachin in 199834. PSS demands that the probability distribution of the generated stego-text ([embedded figure or formula in source report]) perfectly match the distribution of a natural cover-text ([embedded figure or formula in source report]), forcing the Kullback-Leibler divergence to exactly zero. Under these conditions, distinguishing between natural text and stego-text is mathematically equivalent to random guessing35. Adaptive Dynamic Grouping (ADG) was developed specifically to fulfill this rigorous standard31. At each step of text generation, the ADG algorithm intercepts the LLM's predicted probabilities and sorts the entire vocabulary. It then dynamically partitions the vocabulary tokens into [embedded figure or formula in source report] distinct groups, meticulously allocating tokens so that the cumulative probability mass of each individual group is approximately equal to the others35. Each of these [embedded figure or formula in source report] groups corresponds to a specific [embedded figure or formula in source report]\-bit binary integer (ranging from [embedded figure or formula in source report] to [embedded figure or formula in source report])35. To embed a sequence of [embedded figure or formula in source report] secret bits, the ADG algorithm reads the bitstream, identifies the corresponding group, and restricts the sampling pool entirely to the tokens within that selected group. Crucially, the algorithm then samples a token proportionally based on the tokens' normalized probabilities within that group35. Because the groups share equal cumulative probabilities, selecting a group based on a uniformly distributed, pre-encrypted secret bitstream perfectly mirrors the natural probability of that group being selected organically by the LLM. Thus, ADG achieves near-perfect theoretical security. However, this security comes at a cost: ADG incurs substantial computational overhead due to the necessity of repeated dynamic grouping and sorting of tens of thousands of vocabulary tokens at every single generation step32.

Minimum Entropy Coupling and Distribution Copies (Discop)#

An evolution in the pursuit of PSS is the utilization of Minimum Entropy Coupling, operationalized in state-of-the-art algorithms like Discop (Distribution Copies)34. Unlike ADG, which physically constructs discrete token groups, Discop manipulates the probability intervals directly. It assigns each candidate token an interval proportionate to its probability within [embedded figure or formula in source report], and then generates multiple exact "copies" of this overall distribution by rotating all intervals by a predetermined mathematical displacement36. To embed data, the Discop algorithm uses the binary sequence of the secret message to dictate which of the rotated distribution copies the LLM will sample from for that specific token36. Because the probability volume of each token remains identical across all rotated distribution copies, the marginal probability of selecting any given token is strictly equal to the LLM's original, unaltered output distribution36. This guarantees zero Kullback-Leibler divergence. The receiver, possessing the shared secret key—comprising the pseudo-random number generator (PRNG) seed and the identical LLM architecture—recreates the exact rotated distributions to deduce which copy was selected by the sender, thereby recovering the message bit by bit36. Studies comparing Discop to ADG have found that minimum entropy coupling achieves superior encoding efficiency while maintaining stricter provable security constraints34.

Black-Box Applications: LLM-Stega#

The generative techniques described above operate strictly as "white-box" methods; they require granular, backend access to the LLM's internal softmax probability distributions to calculate intervals, Huffman trees, or ADG groups29. In modern deployment scenarios where state-of-the-art proprietary LLMs (e.g., GPT-4, Claude) are gated behind public APIs that output only the final generated text tokens, white-box steganography is rendered completely unfeasible. To circumvent this limitation, researchers developed LLM-Stega, a black-box generative framework29. Rather than manipulating token probabilities, LLM-Stega relies on elaborately constructed prompt engineering. It establishes a pre-encrypted mapping between secret binary bits and a predefined set of semantic keywords29. The sender prompts the LLM to generate a natural response on a specific topic while forcing the inclusion of the mapped keywords. To ensure the reliability of the covert channel and the naturalness of the prose, LLM-Stega incorporates a rejection-sampling optimization mechanism: if the generated text fails to embed the keywords in the correct sequence, or if the resulting text exhibits a highly unnatural semantic flow, the generation is rejected, discarded, and reprompted29. This technique decouples the steganographic mapping from the LLM’s internal generation architecture, allowing it to operate effectively across arbitrary user interfaces and API endpoints29.

Metrics of Efficacy: Payload, Imperceptibility, and Reliability#

The viability and operational danger of a linguistic steganographic system are evaluated across three heavily contested axes: embedding capacity (payload), imperceptibility to detection, and the reliability of message extraction.

Information Capacity (Payload)#

Capacity in linguistic steganography is universally quantified in Bits Per Word (BPW) or Bits Per Token. Classical modification methods, such as Winstein's T-Lex or Chang's Vertex Coding, operate under severe capacity ceilings, typically yielding payloads of roughly 1 to 2 bits per sentence, or approximately 0.1 BPW. This limitation stems from the fact that only a minor fraction of words in a natural sentence possess viable synonyms that can be swapped without destroying context25. Generative LLM models increase capacity exponentially by utilizing every generated token as a potential carrier. In empirical evaluations, Arithmetic Coding can achieve varying payloads depending on the truncation parameters applied to the vocabulary and the innate entropy of the LLM; configurations like AC-6 can embed nearly 3.99 BPW41. In comparative testing, ADG has been shown to embed approximately 5.63 BPW, whereas Discop yields around 4.76 BPW, prioritizing absolute provable security over maximizing raw capacity39. Conversely, black-box methods like LLM-Stega have reported payloads reaching up to 5.93 BPW. By mapping dense binary clusters to broader semantic keywords rather than attempting to manipulate individual token generation steps, LLM-Stega achieves exceptional data density39.

Imperceptibility Metrics#

Imperceptibility is the ultimate safeguard against algorithmic steganalysis. It is assessed both subjectively via human evaluation panels and objectively through a triad of statistical metrics30.

1. Perplexity (PPL): PPL measures how well a language model predicts a sample text. A high perplexity indicates unnatural, disjointed, or surprising text structure. A successful generative steganography algorithm must produce text with a PPL closely matching natural baselines. In testing, normal English sentences exhibit an average PPL of 185.64; LLM-Stega successfully generates stego-texts with a highly comparable PPL of 165.76, rendering it statistically normal39. 2. Kullback-Leibler Divergence (KLD): KLD computes the mathematical difference between the natural text's expected probability distribution and the stego-text's actual distribution. Provably secure methods like Discop aim to drive KLD exactly to zero, ensuring perfect statistical indistinguishability36. 3. Semantic Similarity (SS): SS evaluates the logical flow and contextual coherence of the text, typically measured using embedding distances like BERT feature representations. While Discop excels in SS by strictly mirroring natural distributions, rule-based synonym systems historically struggle with contextual fitness39. Notably, algorithms like Discop can sometimes achieve a PPL that is too low (e.g., 46.73), which ironically can flag the text as highly artificial or machine-generated, despite being semantically sound39.

Extraction Reliability and Tokenization Inconsistency#

A persistent and fatal vulnerability in generative steganography is extraction reliability, primarily caused by the phenomenon of tokenization inconsistency14. When an LLM processes text, words are segmented into sub-word tokens. The sequence of tokens generated on the sender's side (Alice) may be parsed differently by the receiver's model (Bob) depending on minute shifts in whitespace, casing, or upstream context. Because generative algorithms like AC, ADG, and Discop rely on the precise, sequential probability distribution of the LLM to decode the message, if a single token is misaligned or tokenized differently by the receiver, the synchronized extraction chain is shattered. This misalignment destroys the entire downstream payload. Advanced steganographic systems mitigate this fatal flaw through strict prompt constraints, aggressive vocabulary truncation (excluding highly volatile or non-deterministic tokens from the embedding pool), and the overlaying of robust error-correction coding (such as Hamming or Reed-Solomon codes) onto the bitstream prior to embedding14.

Linguistic Steganalysis: The Science of Covert Detection#

Where steganography seeks to conceal, steganalysis seeks to expose. The continuous refinement of steganographic algorithms has precipitated a hostile arms race with steganalysis methodologies40. The primary objective of the steganalyzer (Eve) is to determine, with a high degree of statistical confidence, whether a given text is a natural cover or a covert stego-text.

Statistical Mimicry Flaws and Relative Frequency Analysis#

For injection-based systems utilizing synonym substitution, the earliest and most devastating detection mechanisms relied on macroscopic statistical anomalies. Natural language fundamentally adheres to Zipf’s Law, which dictates that a word's frequency is inversely proportional to its rank in the frequency table. Furthermore, within any given synset, human writers naturally prefer certain synonyms over others based on dialect, genre, or common usage conventions12. When a substitution steganography algorithm encrypts a message, it acts upon a uniformly distributed, high-entropy binary sequence (resulting from the pre-encryption of the payload). Consequently, the algorithm selects synonyms uniformly to map to these bits, choosing highly obscure words just as frequently as exceedingly common words43. Researchers such as Chen, Yang (2011), and Xiang (2014) pioneered Relative Frequency Analysis (RFA) to explicitly exploit this vulnerability43. RFA calculates the Natural Relative Frequency (NRF) of each synonym within a vast reference corpus. By evaluating the expectation and variance of the NRF values of substituted words against natural texts, steganalyzers can easily identify stego-texts. Natural text maintains high variance in synonym usage (heavily favoring common words), whereas stego-text flattens this distribution, significantly reducing NRF variance and raising a massive statistical red flag43. To counter RFA, steganographers developed Word-Frequency-Preserving algorithms and Synonym Run-Length Encoding25. Rather than simply swapping words directly for bits, these countermeasures digitize the relative word frequencies into binary values and express them as sequential "runs." The algorithm embeds the secret message strictly into the parities of the run lengths by self-adaptively flipping only the boundary elements of adjacent runs. This technique brilliantly preserves the macro-ratio of high-to-low frequency synonyms across the text, drastically reducing statistical distortion and neutralizing RFA steganalysis25.

Deep Learning and Contextual Fitness Steganalysis#

As steganographers adapted to defeat basic frequency tests, steganalyzers evolved by integrating deep learning and word embeddings to evaluate localized semantic coherence. Using neural language architectures like the Skip-gram model (from Word2Vec) or Recurrent Neural Networks (RNNs), modern steganalysis transforms individual words into high-dimensional dense vectors43. These embeddings allow the steganalyzer to calculate a highly precise context fitness score—the mathematical distance between a specific word's semantic vector and the vectors of its surrounding context words43. Because substitution steganography often prioritizes binary bit mapping over ideal semantic placement, the substituted words routinely exhibit lower context fitness scores than natural human choices, allowing SVM classifiers to flag the anomalies43. More recent, state-of-the-art frameworks leverage Two-Stage Cascaded Convolutional Neural Networks (CNNs) to automate feature extraction, utilizing hard negative mining to detect even the subtlest alterations40. This architecture operates in two distinct phases:

1. Sentence-Level Analysis: The first tier applies convolutional kernels of varying window sizes to capture [embedded figure or formula in source report]\-gram relationships and word-association features across a single sentence. Max-pooling layers condense this data, allowing a classifier to output a probability that the sentence contains a steganographic anomaly, generating high-dimensional representations40. 2. Segment/Text-Level Fusion: Because sophisticated adversaries employ extremely low embedding rates—modifying perhaps only one or two words per paragraph to evade detection—a sentence-level anomaly might not trigger an alarm. The second tier aggregates the sentence-level high-dimensional representations. This heterogeneous feature extraction focuses entirely on accumulated minor differences across the entire text, successfully identifying covert communications even at exceptionally low payloads40.

Despite these formidable advances in deep learning, detecting modern Provably Secure Steganography (like ADG or Discop) remains an unsolved challenge. Because these generative models mathematically force the output distribution to perfectly match the LLM's baseline distribution without altering context fitness or flattening word frequencies, CNNs struggle to find any actionable anomalies. In empirical testing, highly advanced steganalysis tools like LS-CNN, BiLSTM-Dense, and Bert-FT are frequently reduced to detection accuracies hovering near 50%—the exact statistical equivalent of random guessing39.

Strategic Implications and Future Horizons#

The trajectory of linguistic steganography points toward a rapidly narrowing gap between machine-generated covert text and human-authored natural text. The immediate second-order effect of LLM-based generative steganography is the obsolescence of injective, format-based, and traditional lexical substitution methods. As algorithms like Discop and LLM-Stega prove capable of embedding dense data streams within highly fluent prose, the reliance on fragile, static synonym databases will evaporate36. Consequently, the task of network wardens and security monitors will shift dramatically. Steganalysis can no longer rely on structural heuristics, NRF variance analysis, or the statistical flattening of word frequencies39. Instead, detection mechanisms will be forced to evaluate the macro-level intent and behavioral consistency of the text, likely necessitating the deployment of adversarial LLMs specifically trained to detect subtle contextual hallucination patterns introduced by the generative embedding logic39. A significant third-order effect is the democratization of covert communication. Historically, implementing resilient algorithms like T-Lex or Vertex Coding required sophisticated cryptographic knowledge, local computational power, and exactingly synchronized lexical databases3. With the advent of black-box LLM steganography, any individual with standard API access to commercial models (e.g., ChatGPT, Claude) can establish an untraceable, high-capacity covert channel29. This paradigm effectively turns the public interfaces of massive tech infrastructure into vehicles for undetectable data exfiltration, posing severe challenges for corporate data-loss prevention protocols, censorship circumvention, and national security monitoring apparatuses1. Furthermore, the theoretical ceiling established by minimum entropy coupling implies that as long as a steganographer is willing to throttle payload capacity, perfect mathematical security is attainable34. This suggests an impending equilibrium in the steganography-steganalysis arms race, where detection becomes practically impossible through text analysis alone. In such a future, exposing a covert channel will rely almost entirely on traditional endpoint compromise or capturing the pre-shared cryptographic keys—such as the PRNG seeds, prompt templates, and keyword mappings—used to initialize the LLM's state, rather than analyzing the resulting text itself14.

Works cited#

1. Steganography: from its origins to the present \- Telsy, https://www.telsy.com/en/steganography-from-its-origins-to-the-present/↗
   Source host: telsy.com
2. Steganography \- Wikipedia, https://en.wikipedia.org/wiki/Steganography↗
   Source host: en.wikipedia.org
3. Practical Linguistic Steganography using Contextual Synonym Substitution and a Novel Vertex Coding Method \- ACL Anthology, https://aclanthology.org/J14-2006.pdf↗
   Source host: aclanthology.org
4. Introduction to Steganography, http://acorn.stanford.edu/psych221/projects/2005/vvikram/stego.htm↗
   Source host: acorn.stanford.edu
5. A Comprehensive Survey on Linguistic Steganography: Methods, Countermeasures, Evaluation, and Challenges \- ResearchGate, https://www.researchgate.net/publication/398488225\_A\_Comprehensive\_Survey\_on\_Linguistic\_Steganography\_Methods\_Countermeasures\_Evaluation\_and\_Challenges↗
   Source host: researchgate.net
6. Modified Linguistic Steganography Approach by Using Syntax Bank and Digital Signature \- International Journal of Information and Education Technology, https://www.ijiet.org/papers/68-R055.pdf↗
   Source host: ijiet.org
7. (PDF) Introduction to Linguistic Steganography \- ResearchGate, https://www.researchgate.net/publication/282468633\_Introduction\_to\_Linguistic\_Steganography↗
   Source host: researchgate.net
8. Manipulating the Perception of Paragraph Breaks: A New Theoretical Model of Textual Steganography Using Paragraphs \- Access Manager \- University of Portsmouth, https://pure.port.ac.uk/ws/portalfiles/portal/76984887/PhD\_Thesis\_UP667302\_Version3.2.pdf↗
   Source host: pure.port.ac.uk
9. (PDF) A Universal Lexical Steganography Technique \- ResearchGate, https://www.researchgate.net/publication/272950392\_A\_Universal\_Lexical\_Steganography\_Technique↗
   Source host: researchgate.net
10. Hashing, Pooling and Coding: Towards Optimal Embedding in Linguistic Steganography, https://www.cs.ox.ac.uk/people/andrew.ker/docs/wilson-linguistic-steganography.pdf↗
    Source host: cs.ox.ac.uk
11. Semantic-Preserving Linguistic Steganography by Pivot Translation and Semantic-Aware Bins Coding \- IEEE Computer Society, https://www.computer.org/csdl/journal/tq/2024/01/10049662/1KYoKNjrRD2↗
    Source host: computer.org
12. (PDF) Applying statistical methods to text steganography \- ResearchGate, https://www.researchgate.net/publication/51944443\_Applying\_statistical\_methods\_to\_text\_steganography↗
    Source host: researchgate.net
13. Transformations for linguistic steganography \- Apollo \- University of Cambridge, https://www.repository.cam.ac.uk/items/f8253945-01f5-44d7-867e-fe5f07de4321↗
    Source host: repository.cam.ac.uk
14. OD-Stega: LLM-Based Relatively Secure Steganography via Optimized Distributions \- ACL Anthology, https://aclanthology.org/2026.eacl-long.36.pdf↗
    Source host: aclanthology.org
15. OD-Stega: LLM-Based Near-Imperceptible Steganography via Optimized Distributions, https://arxiv.org/html/2410.04328v1↗
    Source host: arxiv.org
16. StegChat: A Synonym-Substitution Based Algorithm for Text Steganography Joseph Gardiner \- Lancaster University, https://www.lancaster.ac.uk/pg/gardine1/papers/mscreport.pdf↗
    Source host: lancaster.ac.uk
17. Steganography \- MIT, https://web.mit.edu/keithw/tlex/lsteg.pdf↗
    Source host: web.mit.edu
18. Natural language watermarking via paraphraser-based lexical substitution \- Jipeng Qiang, https://qiang2100.github.io/papers/2023-artifical-intelligence.pdf↗
    Source host: qiang2100.github.io
19. Linguistic Mimicry Steganography, https://www.csc.kth.se/utbildning/kandidatexjobb/datateknik/2010/rapport/bergner\_emil\_K10059.pdf↗
    Source host: csc.kth.se
20. Keith Winstein \- Wikipedia, https://en.wikipedia.org/wiki/Keith\_Winstein↗
    Source host: en.wikipedia.org
21. Towards Linguistic Steganography: A Systematic Investigation of Approaches, Systems, and Issues \- Dr Richard Bergmair, https://richard.bergmair.eu/dwn/Bergmair2004Bb5.pdf↗
    Source host: richard.bergmair.eu
22. (PDF) Attacks on Lexical Natural Language Steganography Systems \- ResearchGate, https://www.researchgate.net/publication/249915757\_Attacks\_on\_Lexical\_Natural\_Language\_Steganography\_Systems↗
    Source host: researchgate.net
23. A Comprehensive Bibliography of Linguistic Steganography \- Dr Richard Bergmair, https://richard.bergmair.eu/dwn/Bergmair2007Asubm.pdf↗
    Source host: richard.bergmair.eu
24. Practical Linguistic Steganography using Contextual Synonym Substitution and a Novel Vertex Coding Method \- MIT Press Direct, https://direct.mit.edu/coli/article/40/2/403/1470/Practical-Linguistic-Steganography-using↗
    Source host: direct.mit.edu
25. A Novel Linguistic Steganography Based on Synonym Run-Length Encoding | Request PDF, https://www.researchgate.net/publication/313233602\_A\_Novel\_Linguistic\_Steganography\_Based\_on\_Synonym\_Run-Length\_Encoding↗
    Source host: researchgate.net
26. Practical Linguistic Steganography Using Contextual Synonym Substitution and Vertex Colour Coding \- ACL Anthology, https://aclanthology.org/D10-1116/↗
    Source host: aclanthology.org
27. (PDF) The English Lexical substitution task \- ResearchGate, https://www.researchgate.net/publication/257547187\_The\_English\_Lexical\_substitution\_task↗
    Source host: researchgate.net
28. Practical Linguistic Steganography Using Contextual Synonym Substitution and Vertex Colour Coding. \- ResearchGate, https://www.researchgate.net/publication/221012938\_Practical\_Linguistic\_Steganography\_Using\_Contextual\_Synonym\_Substitution\_and\_Vertex\_Colour\_Coding↗
    Source host: researchgate.net
29. Generative Text Steganography with Large Language Model \- arXiv, https://arxiv.org/html/2404.10229v2↗
    Source host: arxiv.org
30. \[2010.00677\] Near-imperceptible Neural Linguistic Steganography via Self-Adjusting Arithmetic Coding \- arXiv, https://arxiv.org/abs/2010.00677↗
    Source host: arxiv.org
31. Provably Secure Generative Linguistic Steganography \- ACL Anthology, https://aclanthology.org/2021.findings-acl.268.pdf↗
    Source host: aclanthology.org
32. Linguistic Steganography via Self-Adjusting Asymmetric Number System \- MIT Press Direct, https://direct.mit.edu/coli/article/52/1/113/132854/Linguistic-Steganography-via-Self-Adjusting↗
    Source host: direct.mit.edu
33. Provable Secure Steganography Based on Adaptive Dynamic Sampling \- arXiv, https://arxiv.org/html/2504.12579v3↗
    Source host: arxiv.org
34. ICLR Poster Perfectly Secure Steganography Using Minimum Entropy Coupling, https://iclr.cc/virtual/2023/poster/11490↗
    Source host: iclr.cc
35. SparSamp: Efficient Provably Secure Steganography Based on Sparse Sampling \- USENIX, https://www.usenix.org/system/files/usenixsecurity25-wang-yaofei.pdf↗
    Source host: usenix.org
36. Discop: Provably Secure Steganography in Practice Based on “Distribution Copies” \- Jinyang Ding, https://dingjinyang.github.io/uploads/Discop\_sp23\_paper.pdf↗
    Source host: dingjinyang.github.io
37. (PDF) Provably Secure Generative Linguistic Steganography \- ResearchGate, https://www.researchgate.net/publication/352029330\_Provably\_Secure\_Generative\_Linguistic\_Steganography↗
    Source host: researchgate.net
38. \[2106.02011\] Provably Secure Generative Linguistic Steganography \- arXiv, https://arxiv.org/abs/2106.02011↗
    Source host: arxiv.org
39. Generative Text Steganography with Large Language Model \[Quick Review\] \- Liner, https://liner.com/review/generative-text-steganography-with-large-language-model↗
    Source host: liner.com
40. Synonym Substitution Steganalysis Based on Heterogeneous Feature Extraction and Hard Sample Mining Re-Perception \- MDPI, https://www.mdpi.com/2504-2289/9/8/192↗
    Source host: mdpi.com
41. Generative Text Steganography with Large Language Model \- arXiv, https://arxiv.org/html/2404.10229v1↗
    Source host: arxiv.org
42. \[PDF\] TI-StegoAlign: Channel-Guided Post-Training for Generative, https://www.semanticscholar.org/paper/TI-StegoAlign%3A-Channel-Guided-Post-Training-for-Zhou-Xue/cd4faaf9c3a6bcbfc9ec5996bbc6cfc89b80564a↗
    Source host: semanticscholar.org
43. A convolutional neural network-based linguistic steganalysis for synonym substitution steganography \- AIMS Press, https://www.aimspress.com/article/doi/10.3934/mbe.2020055↗
    Source host: aimspress.com
44. Detection of Synonym-Substitution Modified Articles Using Context Information | Request PDF \- ResearchGate, https://www.researchgate.net/publication/220984759\_Detection\_of\_Synonym-Substitution\_Modified\_Articles\_Using\_Context\_Information↗
    Source host: researchgate.net
45. A convolutional neural network-based linguistic steganalysis for synonym substitution steganography \- AIMS Press, https://www.aimspress.com/fileOther/PDF/MBE/mbe-17-02-055.pdf↗
    Source host: aimspress.com
46. A word-frequency-preserving steganographic method based on synonym substitution | International Journal of Computational Science and Engineering \- Inderscience Online, https://www.inderscienceonline.com/doi/abs/10.1504/IJCSE.2019.099648↗
    Source host: inderscienceonline.com
47. A Novel Linguistic Steganography Based on Synonym Run-Length Encoding \- J-Stage, https://www.jstage.jst.go.jp/article/transinf/E100.D/2/E100.D\_2016EDP7358/\_article↗
    Source host: jstage.jst.go.jp
48. A Word-Embedding-Based Steganalysis Method For Linguistic Steganography Via Synonym Substitution | PDF | Support Vector Machine \- Scribd, https://www.scribd.com/document/833562885/A-Word-Embedding-Based-Steganalysis-Method-for-Linguistic-Steganography-via-Synonym-Substitution↗
    Source host: scribd.com

26 embedded image data references are retained in the raw Markdown source.