Provably Secure Generative Linguistic Steganography

1 Introduction

• Steganography hides secret information in an innocent natural carrier, concealing its existence rather than only its content as cryptography does.The passage notes that concealing existence can make steganography more secure and reliable in some scenarios.Source: §1 · p. 1
• Text can usually travel losslessly through public channels, but its low entropy and limited redundancy often restrict linguistic-steganography capacity.Modification-based approaches such as synonym substitution and spelling transformation have few options if they are to preserve fluency.Source: §1 · p. 1
• Neural language models' progress in fluent text generation has enabled investigation of generation-based linguistic steganography.The passage cites work on language models and generation-based methods.Source: §1 · p. 1
• Earlier generative methods encode secrets through token selection without covertext, alleviating low embedding capacity but introducing generation distortions that threaten imperceptibility.The paper identifies further improvement of imperceptibility as its aim.Source: §1 · p. 1
• ADG adaptively groups tokens by their language-model probabilities at each time step to embed secret information in generated stegotext.The paper reports a mathematical security proof and experimental analysis of imperceptibility and embedding capacity.Source: §1 · pp. 1–2

2.1 Notation

• Bold lowercase letters denote vectors, lowercase letters scalars, uppercase letters sets, and calligraphic letters neural models.The size of a set A is denoted |A|.Source: §2.1 · p. 2
• The notation uses p(·) and q(·) for distributions and f(·) for functions, often shortened to p, q, and f.Subscripts and superscripts distinguish variables, distributions, and functions.Source: §2.1 · p. 2

2.2 Generative Linguistic Steganography

• Language modeling estimates the joint distribution pLM(w) of serialized natural language, where w is a sequence of n tokens from vocabulary Σ.For an autoregressive language model, the output is factorized into conditional distributions of the current token.Source: §2.2 · p. 2
• In the sender–receiver setup, Alice sends Bob a uniformly distributed secret bitstream m through a public channel monitored by Eve.Alice and Bob share an embedding algorithm femb.Source: §2.2 · p. 2
• The embedding algorithm takes language model L and secret message m as input and outputs stegotext y for transmission.The passage describes this as generative linguistic steganography.Source: §2.2 · p. 2
• The shared extraction algorithm fext is the inverse mapping that recovers m from received stegotext y using language model L.Source: §2.2 · p. 2

2.3 Imperceptibility

• Stegotext is required to be fluent and statistically indistinguishable from natural innocuous text, called covertext.Information-theoretic security is defined as the KL divergence between covertext and stegotext distributions.Source: §2.3 · p. 2
• The formalism separates distortion from language-model bias, the gap between ptrue and pLM, from embedding distortion, the gap between pLM and q.Stegosampling is equivalent to sampling from modified distribution q induced by the embedding algorithm; the latter gap also compares conditional token distributions.Source: §2.3 · p. 2

3 Related Work

• Rule-based and Markov-chain approaches were difficult to make grammatically correct and semantically fluent.The cited early approaches include Wayner (1992), Chapman and Davida (1997), Chapman et al. (2001), Chapman and Davida (2002), Dai et al. (2010), Moraldo (2014), Luo et al. (2016), and Yang et al. (2018b).Source: §3 · p. 2
• The method randomly partitioned vocabulary Σ into 2b bins, each containing |Σ|/2b tokens, then at each time step selected the highest-probability token within the bin determined by the b-bit secret information to embed.Source: §3 · p. 3
• The method builds a mapping from secret information to tokens dynamically at each time step, rather than statically in advance.Source: §3 · p. 3
• Patient-Huffman uses Huffman embedding only when distortion is below a preset threshold δ, otherwise sampling directly to avoid high-distortion occasions.The method sacrifices embedding capacity for imperceptibility.Source: §3 · p. 3
• Ziegler et al. (2019) used arithmetic coding on the top h likely tokens, excluding low-probability long tails.The passage says arithmetic coding's higher compression rate results in less damage to pLM's conditional probability distribution and helps improve imperceptibility.Source: §3 · p. 3

4 ADG Methodology

• ADG adaptively groups tokens from an off-the-shelf language model to embed secret information while aiming to minimize embedding-induced distortion.The methodology treats language-model bias as a separate distortion source and focuses on damage caused by the embedding algorithm.Source: §4 · p. 3

4.1 Steganography by Grouping

• Grouping assigns each group a unique secret message; the sender selects a group using secret bits and samples a token from it.The equivalent distribution normalizes token probabilities within a group and weights the selected group by 1/u for uniformly distributed secret information.Source: §4.1 · p. 3
• Under the stated uniform-bitstream assumption, equal-probability groups achieve optimal imperceptibility when the modeled and equivalent distributions coincide.Because token probabilities are discrete, ADG uses a suboptimal grouping procedure, selecting the number of groups from the highest token probability and using binary search to choose a nearby-probability token.Source: §4.1 · pp. 3–4

4.2 Recursion and Pruning

• Recursive grouping continues within the selected group until its normalized maximum token probability exceeds 0.5, while pruning skips redundant operations.This makes the amount of secret information embedded per token depend dynamically on the probability distribution.Source: §4.2 · p. 4

20 end

• The authors extend the security proof for equal grouping to recursive ADG, concluding that the proposed method is provably secure.The recursion repeats grouping according to the conditional distribution and secret information until the selected group is indivisible.Source: §20 · p. 5

4.3 Information Extraction

• Exact extraction requires Alice and Bob to share the language model, vocabulary, and grouping algorithm; the selected group indices reveal the embedded secret.Bob reproduces the grouping at each step and selects the group containing the current stegotext token.Source: §4.3 · p. 5

5.1 Datasets

• The evaluation uses Movie, News, and Tweet corpora, including reviews, news publications, and tweets.The reported corpus sizes include 100,000 movie reviews and 1,600,000 tweets.Source: §5.1 · p. 5

5.2 Implementation Details

• The experiments use word-level generation with two-layer LSTMs and select the language model performing best on the test sets.The models were trained for 30 epochs; generated sentences were constrained to be longer than 5 and shorter than 200 tokens.Source: §5.2 · pp. 5–6

5.3 Baselines

• The baselines are Bins, Huffman, Patient-Huffman, and Arithmetic, rebuilt using the same language models for fair comparison.The experiments generated 1,000 stegotexts per case and sampled an equal number of covertexts from the test sets.Source: §5.3 · p. 6

5.4 Metrics

• The metrics cover embedding rate, KLD1 and KLD2, detection accuracy, and effective embedding rate.Embedding rate measures information per token in bits per word; higher is better, while lower KLD values are better. Effective embedding rate is proposed as a comprehensive performance metric.Source: §5.4 · pp. 6–7

5.5 Results and Analysis

• ADG outperforms all baselines on KLD1 and approaches the optimal value 0, while its KLD2 results indicate statistical consistency with covertext.Patient-Huffman at δ = 1.0 also performs well on KLD2, but the authors note its embedding-capacity flaw; Table 1 reports ER, KLD1, and KLD2.Source: Table 1 · p. 6, §5.5 · p. 7
• On three corpora, ADG outperforms all baselines in antisteganalysis and is close to the optimal detection accuracy of 0.5.The authors say the antisteganalysis tendency coheres with the KLD results; Table 2 reports ER, Acc1, and Acc2.Source: §5.5 · p. 7, Table 2 · p. 7
• ADG-generated stegotext is reported to have fluent text, correct grammar, and coherent semantics, with examples from all three corpora shown in Table 5.The examples are presented as a qualitative study.Source: §5.5 · p. 8, Table 5 · p. 8
• ADG outperforms all baselines on effective embedding rate, which accounts for both embedding capacity and imperceptibility.The authors report this as its excellent comprehensive performance; Table 4 reports ER, EER1, and EER2.Source: §5.5 · p. 8, Table 4 · p. 8

• Previous generative linguistic steganography methods inevitably distort distributions estimated by off-the-shelf language models.Source: §6 · p. 8
• ADG is reported provably secure and capable of generating fluent stegotext with high embedding capacity and high imperceptibility.Source: §6 · p. 8
• ADG embeds secret information through adaptive dynamic grouping during stegotext generation.Source: §6 · p. 8
• The authors hope provably secure generative linguistic steganography can serve as a building block for future research.Source: §6 · p. 8