Efficient Provably Secure Linguistic Steganography via Range Coding Ruiyi Yan and Yugo Murawaki Graduate School of Informatics, Kyoto University [email protected], [email protected]
Abstract
s6$*j1%H&Y*($
arXiv:2604.08052v1 [cs.CL] 9 Apr 2026
Key
Linguistic steganography involves embedding secret messages within seemingly innocuous texts to enable covert communication. Provable security, which is a long-standing goal and key motivation, has been extended to language-model-based steganography. Previous provably secure approaches have achieved perfect imperceptibility, measured by zero Kullback–Leibler (KL) divergence, but at the expense of embedding capacity. In this paper, we attempt to directly use a classic entropy coding method (range coding) to achieve secure steganography, and then propose an efficient and provably secure linguistic steganographic method with a rotation mechanism. Experiments across various language models show that our method achieves around 100% entropy utilization (embedding efficiency) for embedding capacity, outperforming the existing baseline methods. Moreover, it achieves high embedding speeds (up to 1554.66 bits/s on GPT-2). The code is available at § github.com/ryehr/RRC_steganography.
1
Introduction
Linguistic steganography, as a promising field in safeguarding information, refers to the art of concealing messages within texts. With rapid advancements in large language models (LLM) (Brown et al., 2020; Achiam et al., 2023; Anthropic, 2024), LM-based steganography methods (Ziegler et al., 2019; Wu et al., 2024; Yan et al., 2025) have dominated linguistic steganography, as leveraging LMs can create flexible text content, diverse genres, and consistent contexts, enabling high embedding capacity. Figure 1 illustrates how a sender (Alice) and a receiver (Bob) communicate using linguistic steganography. Simmons’s “Prisoners’ Problem” (Simmons, 1984) illustrates a steganographic scenario, where Alice and Bob (steganographers) are trying to
Message: 1010011…
Please introduce the Renaissance.
PRNG
LM
Context
Shared
Shared
…
…
+
+
Embedding algorithm
Extraction algorithm
Message: 1010011…
Public channel
Alice
Stegotext
Stegotext
Bob
The Renaissance was a remarkable period of cultural, intellectual, and artistic revival in Europe, spanning roughly from …
Figure 1: A schematic diagram of linguistic steganography, where PRNG refers to a pseudo-random number generator for controlling randomness and reproducibility. Alice embeds the secret message into a steganographic text (stegotext), and Bob extracts the secret message from the received stegotext.
hatch an escape plan, and they can only communicate under the scrutiny of a warden, Eve (a steganalyzer), who can block communication if any suspicious content is detected. To evade detection, they embed their secret message into an innocent-looking carrier (steganographic content). Intuitively, steganographic content is expected to closely resemble normal content, leading to the concept of steganographic security. However, incorporating steganographic algorithms into the language model’s prediction and sampling processes often introduces distributional distortions (Holub and Fridrich, 2013; Yang et al., 2019b). To address this challenge, recent work has explored approaches aimed at achieving provable security (Hopper et al., 2002, 2009) in steganography. Despite the progress of provably secure approaches, each method has its own limitations. ADG (Zhang et al., 2021) fails to strictly preserve the original probability distribution by grouping
candidate tokens at each generative step. Meteor (Kaptchuk et al., 2021), which is based on arithmetic coding (AC) (Ziegler et al., 2019), inevitably distorts the original distribution when encoding intervals. Although iMEC (de Witt et al., 2023), Discop (Ding et al., 2023), and SparSamp (Wang et al., 2025) maintain the original probability distribution, the first two suffer from limited embedding capacity and slow embedding speeds. SparSamp, the current state-of-the-art method, still falls short of achieving full embedding efficiency (i.e., 100% entropy utilization). All of these methods process the secret message as discrete bits, which can result in losses in embedding efficiency or imperceptibility when incorporating some mechanisms for unique extraction. These limitations motivate us to revisit a classical entropy-coding technique, range coding (RC; Martin, 1979) which encodes messages in decimal form rather than in bits, and explore whether it can achieve (i) preservation of the original probability distribution, (ii) full embedding efficiency, and (iii) high embedding speed.1 We begin by proposing a vanilla RC steganography (Section 3). To the best of our knowledge, it is the first attempt to embed a secret message entirely in decimal form. However, we discover its security issues: (1) distortion on probability distribution and (2) randomness reuse. To address these issues, we present rotation range-coding (RRC) steganography, which incorporates a rotation mechanism (Section 4). This mechanism ensures zero KL divergence at every generative step and prevents reuse of randomness. The method is training-free and plug-and-play. In addition, we provide theoretical analysis and proofs regarding zero KL divergence and computational security, supporting the provable security of our RRC steganography (Section 5). Additionally, the approximate 100% entropy utilization for embedding capacity is analyzed and empirically validated. The key advantage of RC-based steganography is ensuring unique extraction internally, without requiring any trade-offs or external restrictions. Experimental results in various language models demonstrate that RRC steganography consistently achieves the highest embedding efficiency (i.e., entropy utilization) and great embedding speed (up to 1554.66 bits/s in GPT-2) compared to all 1 When all operations are carried out in decimals, the original distribution at each generative step is rescaled to a new range, without distortion caused by constructing discrete bits.
provably secure baseline methods (Section 6). Experiments also show that RRC steganography has strong scalability and anti-steganalysis capacity.
2
Background and Preliminaries
2.1
Language Model Basics
A language model (LM) has a vocabulary V, a set of tokens. Consider a sequence of LM-generated T tokens {s(t) } ∈ V T . Tokens with negative indices, [s(−Np ) , . . . , s(−1) ], represent a prompt of length Np and [s(0) , . . . , s(T −1) ] are tokens generated by an LM in response to the prompt. The next token prediction by an LM at position t, is a function whose input is a sequence of known tokens [s(−Np ) , . . . , s(t−1) ] which consists of a prompt and the first t − 1 LM-generated tokens. Then it outputs a logit vector, corresponding to each token in V. These logits are then converted into a discrete probability distribution (t) (t) p(t) = (p1 , . . . , p|V| ) over the vocabulary, via a softmax operator (commonly). The next token is then sampled from p(t) using either standard multinomial sampling, beam search, or other strategies. 2.2
LM-based Steganography
Alice (the sender) wants to communicate a secret message ms ∼ U ({0, 1}l ) with Bob (the receiver) by embedding it in a natural-language text ts (a stegotext). Alice and Bob have agreed on an embedding function Semb and an extracting function Sext that perform steganography, achieved by a language model, M. These two functions are supposed to be invertible. In other words, Semb (M, ms ) = ts , Sext (M, ts ) = m′s . 2.3
Security of Steganography
Cachin (1998) first modeled steganographic security from the perspective of information theory, where given an object x, the security of a stegosystem can be quantified by Kullback-Leibler (KL) divergence between the cover distribution (the channel distribution) Pc and the stego distribution Ps , DKL (Pc ||Ps ) =
X x∈C
Pc (x) log
Pc (x) Ps (x)
(1)
which typically measures how different the two distributions are. When DKL (Pc ||Ps ) = 0, the stegosystem is considered to be perfectly secure in this perspective of information theory. Benefiting from the explicit generative models that can predict probability distributions, the above
definition of(insteganographic security can be modHistorical tokens text form): Drinkingeled contaminated water can increase into another goal, the that is, steganography is risk of infection with Escherichia
Previous tokens (in text form): Drinking contaminated water can increase the risk of infection with Escherichia
indistinguishable from the normal generation process, i.e., random sampling (Ding et al., 2023). LM In addition, from the perspective of computational security (Hopper et al., 2002; Katzenbeisser Predict the next token and Petitcolas, 2002), steganography is secure Candidate pool against chosenProbability hiddentext attacks, if for all probapool coli 99.5% bilistic polynomial time (PPT) adversary detection species AD , it holds: 0.3% albertii
Probability distribution
species (10) albertii (110)
fergusonii 0.1% |Pr[AD (xs ) = 1] − Pr[AD (xc ) = 1]| < negl(λ)
110 2.4 111
Statistical 12.5% Imperceptibility of LM-based 12.5% Steganography
Following the previous formulation (Dai and Cai, 2019; Shen et al., 2020), statistical imperceptibility refers to the similarity between the true language model Mt in the monitored channel and Ms , the language model M integrated with steganographic algorithms. Specifically, the total variation distance (TVD) is used to measure statistical imperceptibility. Consider the TVD between Mt and Ms , i.e. d(Mt , Ms ), by triangle inequality: d(Mt , Ms ) ≤ d(Mt , M) + d(M, Ms ).
95%
coli (0)
0.1%
(2) Huffman encoding where xs is the stegotext, xc is the normally generated cover text, λ is the security parameter of Code Changed probability the shared key K (usually the length of K), and 0 50% negl(λ) is a negligible function concerning λ. 10 25%
Predict the next token
LM
fergusonii (111)
50% 3% 25% 1% 12.5%
Original probability Distorted probability
1% 12.5% 0%
20%
40%
60%
80%
100%
Figure 2: An example of how steganographic encoding (using Huffman coding (Yang et al., 2019b)) can alter the original top-4 probability distribution predicted by a language model. Specifically, a pair such as coli (0) denotes a candidate token along with its Huffman code, and the distorted probabilities are computed based on a random secret message.
In this low-entropy example, “coli” has an overwhelmingly high probability of being the next token, making any alternative token extremely unlikely. If steganography introduces distribution distortion (such as through Huffman encoding), it may create detectable patterns that could be exploited by a steganalysis detector.
(3)
As d(Mt , M) is a criterion to measure the original language model, which is limited by the research on language models. Thus, d(M, Ms ) is the main focus of linguistic steganography. According to Pinsker’s inequality (Fedotov et al., 2003) and additivity of KL divergence, d(M, Ms ) can be further decomposed in each step, that is: v u ∞ u ln 2 X s d(M, M ) ≤ t DKL (p(t) ||p̂(t) ) (4) 2 t=1
where p(t) is the original probability distribution at tth step, and p̂(t) is transformed from p(t) via sampling and encoding. Hence, linguistic steganography could aim to minimize DKL (p(t) ||p̂(t) ), in order to obtain relative near-imperceptibility. Some derivation is skipped here, as details are verified in (Dai and Cai, 2019; Shen et al., 2020; Fedotov et al., 2003). Specifically, Figure 2 illustrates how distribution distortion can compromise imperceptibility.
2.5
Related Work with Zero KL Divergence
Achieving DKL (p(t) ||p̂(t) ) = 0 (for each t) is a desirable objective in steganography. Ding et al. (2023) proposed Discop, a representative zero-KL provably secure steganographic method. At each generative step, the message determines which distribution copy to sample. However, Discop must avoid overlaps between its rotated copies to keep extraction unique: whenever overlaps occur, it embeds fewer bits. Recently, Wang et al. (2025) introduced SparSamp, which embeds messages by combining them with pseudo-random numbers to obtain message-derived random numbers for sampling. To achieve uniquely extractable, SparSamp must sparsify its sampling grid, which leaves a small capacity gap. More related methods and details are shown in Appendix A.
3
Vanilla Range-Coding Steganography
In this section, we tentatively start by describing a simple vanilla version of range-coding (RC)
LM
LM
Predict (t = 0)
0
Predict (t = 1)
0
0 0.3
p1(0) = 0.65
0.65 0.95 1
20219 ∈ 42598.4
p2(0) = 0.3 …
62259.2 65536 (216)
0.8
1
p1(1) = 0.3
Algorithm 1 Vanilla RC steganography (embed)
LM
12779.52
Input: Context (initial previous tokens), C Language model, M Message length, l Secret message, ms
34078.72
Output: Steganographic text, ts
Predict (t = 2)
0 12779.52
p2(1) = 0.5
20219 ∈
…
34078.72 42598.4
0 …
1
16-bit secret message: 0100111011111011 Decimal value: 20219
Figure 3: An example of procedures for embedding a 16-bit secret message into a text via the vanilla RC steganography. The interval is iteratively narrowed until it can uniquely represent the decimal value 20219.
steganography, which directly applies RC to linguistic steganography. 3.1
Embedding & Extraction
Figure 3 briefly illustrates how vanilla RC steganography embeds a message into a text. In range coding, all the information can be represented in decimals and ranges (intervals). In this example, the 16-bit message is interpreted as an integer whose decimal representation is 20219, and the interval is initialized as [0, 216 ) = [0, 65536). Algorithm 1 outlines how the sender (Alice) embeds the secret message ms into the text ts using vanilla RC steganography. Specifically, ms is first decimalized to ds in Line 1, and all subsequent procedures operate directly on ds rather than on a bitstream. In Line 2, the initial interval is set to [0, 2l ), where l is the length of ms . During subsequent iterative processes (Lines 3–9), the interval is progressively narrowed at each step. The iteration ends when the midpoint of the interval is exactly rounded to ds (which ensures uniqueness). Algorithm 2 outlines how the receiver (Bob) extracts the secret message ms from the received text ts . The initial interval is narrowed according to each token received, and ds is the rounded value of the midpoint of the final interval. Finally, the extraction result ms is binarized from ds . 3.2
Security Issues
For vanilla RC steganography, there can be two security issues: 1) Distortion on probability distribution. Taking the first generative step in Figure 3 as an example, (0) the (softmax) probability of token1 (t = 0), p1 , is 0.65, and its interval is [0, 42598.4). Considering a
1: ds ← bin2dec(ms ); // Decimalize 2: [L, R) ← [0, 2l ); // Initialize interval 3: while round( L+R ) ̸= ds do 2 (t) 4: p ← M(C); // Predict probs 5: c(t) ← 0||p(t) .cumsum(); // Cumulate probs 6: c′(t) ← L + (R − L) × c(t) ; // Rescale 7: Select tokeni so that ds ∈ [c′(t) [i − 1], c′(t) [i]); 8: [L, R) ← [c′(t) [i − 1], c′(t) [i]); 9: C ← C||tokeni ; 10: Detokenize C into ts ; 11: return ts
Algorithm 2 Vanilla RC steganography (extract) Input: Context (initial previous tokens), C Language model, M Message length, l Steganographic text, ts Output: Secret message, ms 1: Tokenize ts into S; 2: [L, R) ← [0, 2l ); // Initialize interval 3: for t = 0, 1, . . . , |S| − |C| − 1 do 4: p(t) ← M (S [: |C| + t]); // Predict probs 5: c(t) ← 0||p(t) .cumsum(); // Cumulate probs 6: c′(t) ← L + (R − L) × c(t) ; // Rescale 7: Select tokeni so that tokeni = S [|C| + t + 1]; 8: [L, R) ← [c′(t) [i − 1], c′(t) [i]); 9: ds ← round( L+R ); 2 10: ms ← dec2bin(ds ).zfill(l); // Binarize & Fill 0 11: return ms
random 16-bit secret message ms ∼ U ({0, 1}16 ), so ds ∼ U ({0, 1, . . . , 216 − 1}) (ds is a discrete uniform random variable). Then, the steganographic sampled probability for token1 (t = 0) (0) is P (ds ∈ [0, 42598.4)) = 42599 65536 ̸= 0.65 = p1 . Thus, distortion on probability distribution occurs and zero KL divergence or perfect security cannot hold. Even though it could be mitigated when lengthening ms (l can be set greater than the tensor precision). However, similar to AC-based steganography, iterative interval narrowing still causes noticeable distortion in small intervals. 2) Randomness reuse. According to Kaptchuk et al. (2021), reusing randomness in multiple sampling events could expose features and bias to detec-
Algorithm 3 Rotation RC steganography (embed)
Algorithm 4 Rotation RC steganography (extract)
Input: Context (initial previous tokens), C Pseudo-random number generator, PRNG Language model, M Symmetric key (seed), K Message length, l Secret message, ms
Input: Context (initial previous tokens), C Pseudo-random number generator, PRNG Language model, M Symmetric key (seed), K Message length, l Steganographic text, ts
Output: Steganographic text, ts
Output: Secret message, ms
(−1)
1: ds ← bin2dec(ms ); // Decimalize 2: PRNG.set_seed(K); 3: [L(−1) , R(−1) ) ← [0, 2l ); // Initialize interval 4: for t = 0, 1, . . . do 5: p(t) ← M(C); // Predict probs 6: c(t) ← 0||p(t) .cumsum(); // Cumulate probs 7: ∆(t−1) = R(t−1) − L(t−1) ; 8: c′(t) ← L(t−1) + ∆(t−1) × c(t) ; // Rescale 9: o(t) ← U (0, 1).sample(PRNG(t) ); (t) (t−1) 10: ds ← L(t−1) + (ds − L(t−1) + o(t) × (t−1) (t−1) ∆ ) mod ∆ ; // Rotate (t) 11: Select tokeni so that ds ∈ [c′(t) [i − 1], c′(t) [i]); 12: [L(t) , R(t) ) ← [c′(t) [i − 1], c′(t) [i]); 13: C ← C||tokeni ; (t) (t) (t) 14: if L +R − ds ∈ (−0.5, 0.5] then 2 15: break 16: Detokenize C into ts ; 17: return ts
1: Tokenize ts into S; 2: PRNG.set_seed(K); 3: [L(−1) , R(−1) ) ← [0, 2l ); // Initialize interval 4: tend ← |S| − |C| − 1; 5: for t = 0, 1, . . . , tend do 6: p(t) ← M (S [: |C| + t]); // Predict probs 7: c(t) ← 0||p(t) .cumsum(); // Cumulate probs 8: ∆(t−1) ← R(t−1) − L(t−1) ; 9: c′(t) ← L(t−1) + ∆(t−1) × c(t) ; // Rescale 10: Select tokeni so that tokeni = S [|C| + t + 1]; 11: [L(t) , R(t) ) ← [c′(t) [i − 1], c′(t) [i]); 12: mid(tend ) ← (L(tend ) + R(tend ) )/2; 13: for t = tend , . . . , 1, 0 do 14: o(t) ← U (0, 1).sample(PRNG(t) ); 15: mid(t−1) ← L(t−1) + (mid(t) − L(t−1) − o(t) × ∆(t−1) ) mod ∆(t−1) ; // Rotate reversely (−1) ← round_half_down(mid(−1) ); 16: ds (−1) 17: ms ← dec2bin(ds ).zfill(l); //Binarize & Fill 0 18: return ms
tors. Therefore, only using the bits of the message as the randomness or encrypting the message with a pseudo-random cipher, as in a public-key solution, is insecure because multiple samplings will be forced to reuse randomness.
4
Rotation Range-Coding Steganography
Considering the security issues discussed above, we propose a rotation range-coding (RRC) steganographic method. Instead of directly using the constant ds , our proposed rotation mechanism up(t−1) (t) dates ds to ds at each time step t (initial (−1) ds = ds ), with the following objectives: • To transform the discrete uniform random variable ds to a continuous uniform random vari(t) able ds at each t, thereby preserving the original probability distribution and ensuring zero KL divergence. • To introduce fresh randomness at each t, thereby preventing the reuse of randomness. 4.1
Embedding of RRC Steganography
Algorithm 3 outlines the embedding procedures of RRC steganography (Algorithm 3 shares several
steps with Algorithm 1). Inspired by other provably secure methods, we employ a pseudo-random number generator (PRNG) and a symmetric key K to generate pseudo-random numbers for the following sampling (Line 2), ensuring reproducibility and correct extraction. Note that the pseudo-random numbers generated by PRNG are used to control the sampling of the offset o ∼ U (0, 1) at each t (Line (t−1) (t) 9), and then o is used to rotate ds to ds (Line 10). Besides, the termination condition in RRC (t) (t) (t) steganography is L +R − ds ∈ (−0.5, 0.5] 2 (Lines 14–15), which is tailored for unique extraction and avoiding generating unnecessary tokens. 4.2
Extraction of RRC Steganography
Algorithm 4 outlines how the receiver (Bob) extracts the secret message ms from the steganographic text ts . As Alice and Bob have agreed on PRNG and symmetric key K, Bob can synchronize each t-time rotation with Alice and re(t) produce each range of ds according to each interval [L(t) , R(t) ) at each t. Based on the termination condition of the embedding algorithm, the end time tend = |S| − |C| − 1, and mid(tend ) =
(L(tend ) + R(tend ) )/2, there is: end ) mid(tend ) − d(t ∈ (−0.5, 0.5] s end ) d(t ∈ [mid(tend ) − 0.5, mid(tend ) + 0.5). s
Considering linear transformation and the rotation in embedding, for each t there is (in Line 15):
′(t) ′(t) P d(t) ∈ [c [i − 1], c [i]) s Z c′(t) [i] c′(t) [i] − c′(t) [i − 1] fd(t) (x) dx = = s ∆(t−1) c′(t) [i−1] P P (∆(t−1) × ik=1 pk ) − (∆(t−1) × i−1 k=1 pk ) = (t−1) ∆ i i−1 X X = pk − pk = pi . k=1
mid(t−1) = L(t−1) + (mid(t) − L(t−1) − o(t) × ∆(t−1) ) mod ∆(t−1) (t) d(t) − 0.5, mid(t) + 0.5) s ∈ [mid
k=1
Therefore, the probability of selecting tokeni is (t) exactly pi , the original LM distribution.
d(−1) ∈ [mid(−1) − 0.5, mid(−1) + 0.5) s
As RRC steganography does not change the original predicted probability by the LM for each token, the KL divergence between the original and the steganographic probability distribution is zero. RRC steganography possesses perfect statistical imperceptibility (according to Section 2.4).
d(−1) = round_half_down(mid(−1) ) s
5.2
where ∆(t−1) = R(t−1) − L(t−1) . After iteration, (−1) as ds ∈ Z, there is (Line 16):
where round_half_down means that when a number is exactly halfway between two possible rounded values (e.g., 2.5), round_half_down rounds toward the smaller rounded values (e.g., 2). (−1) Therefore, in RRC steganography, ds can be computed uniquely by Bob, and then ms is bina(−1) rized from ds (Line 17).
5
Analysis of RRC Steganography
5.1
Proof of Zero KL Divergence
Considering rotation, we first introduce Proposition 1 (the rigorous proof is shown in Appendix B.1), and then explain how the original probability distribution is preserved (Proposition 2). (t)
Proposition 1. ds ∼ U (L(t−1) , R(t−1) ).
Computational Security
From the perspective of computational security (Section 2.3 and Equation 2), we prove our RRC steganography is a secure method, for which details are shown in Appendix B.3. 5.3
Embedding Capacity
First, we consider when the embedding ends according to the proposed termination condition, there is a proposition (its proof is shown in Appendix B.2): Proposition 3. ∆(t) ≤ 1 is a sufficient condition (t) (t) (t) − ds ∈ for the embedding termination L +R 2 (−0.5, 0.5] (Lines 14–15 in Algorithm 3). Then, given the initial interval [L(−1) , R(−1) ) = [0, 2n ) and the interval length ∆(−1) = 2n , the interval length at t is:
Proposition 2. In Line 11 (Algorithm 3), the se(t) lected probability of each tokeni equals pi . Proof. Considering the interval construction from p(t) to c′(t) (Lines 5–8 in Algorithm 3), p(t) = (t) (t) (t) (t) (t) (p1 , . . . , p|V| ), c(t) = (co , c1 , . . . , c|V| ) = P P|V| (0, 1k=1 pk , . . . , k=1 pk ), and c′(t) = L(t−1) + (t−1) × c(t) = (L(t−1) , L(t−1) + ∆(t−1) × ∆ P1 (t−1) ). According to Proposik=1 pk , . . . , R (t) (t−1) (t−1) tion 1, ds ∼ U (L ,R ), so the probability density function is: ( 1 , if x ∈ [L(t−1) , R(t−1) ), fd(t) (x) = ∆(t−1) s 0, otherwise
∆
(t)
t Y (i) =2 · poutput n
(5)
i=0
and there is: ∆(t) (t) = poutput (t−1) ∆ (i)
(6)
where poutput is the probability of the output token (i = 0, 1, . . . , t). According to Proposition 3, when ∆(t) ≤ 1, the embedding iteration ends. Considering information theory and Equation 5, the interval shrinkage rate is determined by the entropy of the probability distribution. The average amount of information per iteration is H (t) , and the total amount of information is
required to cover n bits of the initial interval. ThereP fore, the number of loops is satisfied: ti=0 H (t) ≥ P|V| (t) (t) n where H (t) = − i=1 pi log2 pi , and let the average entropy is Havg , so that the loop number (which is exactly the number of the generated tokens) is: Ntoken ≈ Hnavg . Thus, the embedding capacity (bits per token) can be represented as: n Ntoken ≈ Havg . RRC steganography can achieve approximate 100% utilization of entropy. 5.4
Complexity
RC-based steganography (including vanilla RC steganography and RRC steganography) requires updating probability intervals after each step, resulting in a time complexity of O(|V|) for each generative step. The complexity can be computed following the approaches used in AC steganography (Ziegler et al., 2019).
6
Experiments
To validate the security and efficiency of our RRC steganography, we evaluated it compared to a series of methods toward provable security in this era, including arithmetic coding (AC) (Ziegler et al., 2019), ADG (Zhang et al., 2021), Meteor (Kaptchuk et al., 2021), iMEC (de Witt et al., 2023), Discop (Ding et al., 2023), and SparSamp (Wang et al., 2025). 6.1
Setup
To validate the generalizability of our steganographic method, we implemented it using three language models of various scales: GPT-2 (Radford et al., 2019),2 OPT-1.3b (Zhang et al., 2022),3 and Llama-2-7b (Touvron et al., 2023).4 For each language model and steganographic method, 1,000 samples were generated using 1,000 different initial contexts. These contexts consist of the first 10 words from sequences randomly selected from the C4 dataset.5 All the experiments were conducted with top-p (p = 1.0) sampling, i.e., encoding the entire vocabulary V, and 1.0 temperature. Experiments were implemented in Python 3.12.7 with Torch 2.5.0, and accelerated by using RTX 6000 Ada Generation GPUs. Besides, considering the precision limitation of the tensor, we imported Python’s decimal 2
https://huggingface.co/openai-community/gpt2 https://huggingface.co/facebook/opt-1.3b 4 https://huggingface.co/meta-llama/Llama-2-7b-hf 5 https://huggingface.co/datasets/allenai/c4 3
module for computing with sufficient precision. Otherwise without an enough precision, errors or incorrect extractions could occur. 6.2
Metrics
Avg (Max) KLD, a security metric, refers to the average (or maximum) value of the KL divergence DKL (p(t) ||p̂(t) ) in all steps, which indicates the average (or maximum) degree to the original distribution by steganography (Ding et al., 2023). Specifically, in DKL (p(t) ||p̂(t) ), p(t) is the probability distribution of the original candidate pool, and p̂(t) is the probability distribution of the modified (steganographic) candidate pool at each t. Embedding capacity refers to the average number of bits embedded per generated token. Entropy utilization (embedding efficiency) refers to the ratio of embedding capacity to the average entropy over all steps. Embedding speed refers to the average seconds required to embed a single secret bit. 6.3
Main Results
Table 1 presents the average results across various metrics for GPT-2. Besides, the results for OPT1.3b and Llama-2-7b are shown in Tables 4 and 5 in Appendix C.1. Both Meteor and Discop were evaluated in two configurations: sorted and unsorted. For each metric, the best-performing result is highlighted in bold, while the second-best is indicated with underline. The embedded secret message was a randomly generated 128-bit sequence. In addition, multinomial sampling generation (random sampling) was also carried out for comparison. The key findings from these experiments are as follows: 1) As analyzed in Wang et al. (2025), iMEC, Discop and SparSamp are probability-preserving. The zero KL divergence of RRC steganography is proved in Section 5.1, thus these methods and our RRC steganography can achieve 0 KL divergence. 2) Our RRC steganography empirically achieves around 100% entropy utilization, which complies with the theoretical analysis in Section 5.3, which denotes the 100% embedding efficiency. Besides, the entropy utilization of our method is steadily superior to other baseline methods when implemented in different language models. 3) Our RRC steganography achieves a highly competitive embedding speed, which is the fastest in GPT-2 (up to 1554.66 bits/s). However, in the other two language models, our method obtains the second-fastest speeds.
Method Multinomial sampling AC ADG Meteor w/o sort Meteor w/ sort iMEC Discop w/o sort Discop w/ sort SparSamp RRC steganography (ours)
Avg / Max KLD ↓ (bits/token) 0/0 1.95E-03 / 3.01E-02 1.60E-04 / 1.57E-03 4.22E-02 / 1.16E-01 4.11E-02 / 1.16E-01 0/0 0/0 0/0 0/0 0/0
Capacity ↑ (bits/token) N/A 5.86 4.81 4.17 4.77 4.16 2.31 5.58 5.74 5.93
Entropy (bits/token) 5.86 5.87 5.89 5.79 5.81 5.83 5.90 5.86 5.93 5.93
Utilization ↑ (%) N/A 99.83 81.60 71.96 82.08 71.44 39.31 95.17 96.76 99.98
Speed ↑ (bits/s) N/A 1025.36 36.45 950.27 25.25 27.30 218.34 44.30 1267.82 1554.66
Table 1: Quantitative comparison with previous steganographic methods on GPT-2. Message length (bits) Utilization (%) ↑ Speed (bits/s) ↑ Running time (s)
32
64
128
256
512
1024
2048
4096
8192
99.86 1390.23 0.023
99.19 1496.88 0.043
99.98 1554.66 0.082
99.89 1572.40 0.163
99.77 1475.68 0.374
99.93 1511.83 0.677
100.35 1191.88 1.718
100.43 880.82 4.650
99.99 604.76 13.546
Table 2: Average results on utilization, speed and running time of RRC steganography across various message lengths l on GPT-2.
Additionally, Appendix C.5 presents ablation studies comparing vanilla RC (Section 3) and provable secure RRC steganography (Section 4). 6.4
Scalability of RRC Steganography
Steganography based on range coding has a distinct characteristic, that is, it embeds the entire secret message using decimal values, rather than embedding it bit by bit. In other words, the minimum unit of embedding is the complete l-bit message itself. If the embedding process is not completed, the message is considered not embedded at all. Therefore, scalability should be considered, as it reflects how well RRC steganography can support the secret message with various lengths. Table 2 lists the average utilization, speed, and running time when RRC steganography embeds the secret message with various lengths on GPT-2. Tables 6 and 7 (in Appendix C.2) show results conducted in OPT-1.3b and Llama-2-7b. The number of generated texts for each message length is 1000. From this table, we can find that: 1) RRC steganography maintains steady entropy utilization around 100%.6 2) When the message length varies from 64 to 1024 bits, the embedding speed is steadily around 1500 bits per second. 6 The stability outperforms SparSamp whose utilization is sensitive to message length and the maximum length is only 1023 (according to the data disclosed in Wang et al. (2025)).
3) Our method supports messages with significantly higher bit lengths (with 8192 bits not representing an upper limit), enabled by the scalable precision of Python’s decimal module. 6.5
Anti-steganalysis Capacity
In this section, we evaluated the ability of our method to evade Eve’s detection using steganalysis techniques, specifically through a fine-tuned discriminator. The discriminators used for detection were fine-tuned versions of the pretrained BERT (Devlin et al., 2019) and RoBERTa (Conneau et al., 2019) models, respectively. Table 8 in Appendix C.3 presents the steganalysis accuracies for steganographic texts generated by three different language models. Accuracies around 50% indicate that the steganalysis methods do not perform better than random guessing in detecting texts. 6.6
Human Evaluation
We randomly mixed the steganographic texts and cover texts (250 samples per category) and asked three human evaluators to judge whether each text was machine-generated with embedded hidden information. As shown in Table 3, the consistently low detection scores indicate that human evaluators struggle to distinguish steganographic texts from cover texts, providing strong evidence for the perceptual imperceptibility of RRC steganography. Notably, statistical classifiers already outperform
Model
Accuracy
Precision
Recall
F1
GPT-2 OPT-1.3B Llama-2-7B
47.8% 46.6% 50.6%
47.8% 46.2% 50.6%
47.2% 41.2% 52.4%
47.5% 43.6% 51.5%
Table 3: Human evaluation results across different models.
humans at this discrimination task, as they can aggregate subtle statistical cues that are imperceptible to human readers.
7
for effective monitoring and regulation. We emphasize that future research should develop effective detection and monitoring systems in parallel, ensuring responsible use of steganography.
Conclusion
In this paper, we explore the use of a relatively simple and classical approach, range coding (RC), to achieve provably secure steganography as well as high embedding efficiency and speed. However, two key security challenges arise: (1) distortion of the probability distribution and (2) reuse of randomness. To address these issues, we propose rotation range-coding (RRC) steganography, and provide theoretical explanations and proofs for it. RRC empirically outperforms the baseline methods in both embedding efficiency and capacity, while also achieving competitive embedding speed. Moreover, RRC steganography is training-free, modelagnostic, and straightforward to implement, making it a practical foundation for future extensions to multi-modal steganography and for deployment in real-world, privacy-preserving communication.
Limitations In the symmetric steganographic system based on RRC steganography, Alice and Bob must agree on the secret message length l before the steganographic communication, which is used to initialize the interval [0, 2l ) for both sides and fill “0” in extraction (Line 17 in Algorithm 4). For the analysis of embedding capacity or embedding efficiency (Section 5.3) of RRC steganography, we only explain an approximate 100% entropy utilization for it without rigorous theoretical proofs, but experiments can empirically prove that its utilization is approximate 100%.
References Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, and 1 others. 2023. Gpt-4 technical report. arXiv preprint arXiv:2303.08774. Anthropic. 2024. The claude 3 model family: Opus, sonnet, haiku. https://www-cdn.anthropic.com/ de8ba9b01c9ab7cbabf5c33b80b7bbc618857627/ Model_Card_Claude_3.pdf. Berk Atil, Sarp Aykent, Alexa Chittams, Lisheng Fu, Rebecca J. Passonneau, Evan Radcliffe, Guru Rajan Rajagopal, Adam Sloan, Tomasz Tudrej, Ferhan Ture, Zhe Wu, Lixinyu Xu, and Breck Baldwin. 2025. Nondeterminism of "deterministic" llm settings. Preprint, arXiv:2408.04667. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, and 12 others. 2020. Language models are few-shot learners. In Advances in Neural Information Processing Systems, volume 33, pages 1877–1901. Curran Associates, Inc. Christian Cachin. 1998. An information-theoretic model for steganography. In Information Hiding, pages 306–318, Berlin, Heidelberg. Springer Berlin Heidelberg.
Ethical Considerations
Alexis Conneau, Kartikay Khandelwal, Naman Goyal, Vishrav Chaudhary, Guillaume Wenzek, Francisco Guzmán, Edouard Grave, Myle Ott, Luke Zettlemoyer, and Veselin Stoyanov. 2019. Unsupervised cross-lingual representation learning at scale. CoRR, abs/1911.02116.
While steganography has legitimate applications such as embedding copyright information, it can also be misused for disinformation or to evade censorship. This dual-use nature underscores the need
Falcon Dai and Zheng Cai. 2019. Towards nearimperceptible steganographic text. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 4303–4308, Florence, Italy. Association for Computational Linguistics.
Christian Schroeder de Witt, Samuel Sokota, J Zico Kolter, Jakob Nicolaus Foerster, and Martin Strohmeier. 2023. Perfectly secure steganography using minimum entropy coupling. In The Eleventh International Conference on Learning Representations. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics. Jinyang Ding, Kejiang Chen, Yaofei Wang, Na Zhao, Weiming Zhang, and Nenghai Yu. 2023. Discop: Provably secure steganography in practice based on "distribution copies". In 2023 IEEE Symposium on Security and Privacy (SP), pages 2238–2255. A.A. Fedotov, P. Harremoes, and F. Topsoe. 2003. Refinements of pinsker’s inequality. IEEE Transactions on Information Theory, 49(6):1491–1498. Vojtěch Holub and Jessica Fridrich. 2013. Digital image steganography using universal distortion. In Proceedings of the First ACM Workshop on Information Hiding and Multimedia Security, IH&MMSec ’13, page 59–68, New York, NY, USA. Association for Computing Machinery. Nicholas Hopper, Luis von Ahn, and John Langford. 2009. Provably secure steganography. IEEE Transactions on Computers, 58(5):662–676. Nicholas J. Hopper, John Langford, and Luis von Ahn. 2002. Provably secure steganography. In Advances in Cryptology — CRYPTO 2002, pages 77–92, Berlin, Heidelberg. Springer Berlin Heidelberg. Gabriel Kaptchuk, Tushar M. Jois, Matthew Green, and Aviel D. Rubin. 2021. Meteor: Cryptographically secure steganography for realistic distributions. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, CCS ’21, page 1529–1548, New York, NY, USA. Association for Computing Machinery. Stefan Katzenbeisser and Fabien AP Petitcolas. 2002. Defining security in steganographic systems. In Security and Watermarking of Multimedia Contents IV, volume 4675, pages 50–56. SPIE. Diederik P. Kingma and Jimmy Ba. 2017. Adam: A method for stochastic optimization. Preprint, arXiv:1412.6980. Tri Van Le. 2003. Efficient provably secure public key steganography. Cryptology ePrint Archive, Paper 2003/156.
G Nigel N Martin. 1979. Range encoding: an algorithm for removing redundancy from a digitised message. In Proc. Institution of Electronic and Radio Engineers International Conference on Video and Data Recording, volume 2. Jumon Nozaki and Yugo Murawaki. 2022. Addressing segmentation ambiguity in neural linguistic steganography. In Proceedings of the 2nd Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics and the 12th International Joint Conference on Natural Language Processing (Volume 2: Short Papers), pages 109–116, Online only. Association for Computational Linguistics. Chao Pan, Donghui Hu, Yaofei Wang, Kejiang Chen, Yinyin Peng, Xianjin Rong, Chen Gu, and Meng Li. 2025. Rethinking prefix-based steganography for enhanced security and efficiency. IEEE Transactions on Information Forensics and Security, 20:3287– 3301. Yuang Qi, Kejiang Chen, Kai Zeng, Weiming Zhang, and Nenghai Yu. 2025. Provably secure disambiguating neural linguistic steganography. IEEE Transactions on Dependable and Secure Computing, 22(3):2430–2442. Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, and 1 others. 2019. Language models are unsupervised multitask learners. OpenAI blog, 1(8):9. J. Rissanen and G. G. Langdon. 1979. Arithmetic coding. IBM Journal of Research and Development, 23(2):149–162. Jiaming Shen, Heng Ji, and Jiawei Han. 2020. Nearimperceptible neural linguistic steganography via self-adjusting arithmetic coding. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 303–313, Online. Association for Computational Linguistics. Gustavus J. Simmons. 1984. The Prisoners’ Problem and the Subliminal Channel, pages 51–67. Springer US, Boston, MA. Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, and 1 others. 2023. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13971. Yaofei Wang, Gang Pei, Kejiang Chen, Jinyang Ding, Chao Pan, Weilong Pang, Donghui Hu, and Weiming Zhang. 2025. SparSamp: Efficient provably secure steganography based on sparse sampling. In The 34th USENIX Security Symposium. Jiaxuan Wu, Zhengxian Wu, Yiming Xue, Juan Wen, and Wanli Peng. 2024. Generative text steganography with large language model. In Proceedings of the 32nd ACM International Conference on Multimedia, MM ’24, page 10345–10353, New York, NY, USA. Association for Computing Machinery.
Lingyun Xiang, Shuanghui Yang, Yuhang Liu, Qian Li, and Chengzhang Zhu. 2020. Novel linguistic steganography based on character-level text generation. Mathematics, 8(9). Ruiyi Yan, Chenhui Chu, Zhongliang Yang, and Yugo Murawaki. 2025. A comprehensive survey on linguistic steganography: Methods, countermeasures, evaluation, and challenges. Ruiyi Yan and Yugo Murawaki. 2025. Addressing tokenization inconsistency in steganography and watermarking based on large language models. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pages 7076–7098, Suzhou, China. Association for Computational Linguistics. Ruiyi Yan, Tian Song, and Yating Yang. 2024a. A nearimperceptible disambiguating approach via verification for generative linguistic steganography. In 2024 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pages 1638–1643. Ruiyi Yan, Tian Song, and Yating Yang. 2024b. Tokenfree: A tokenization-free generative linguistic steganographic approach with enhanced imperceptibility. In 2024 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pages 449– 455. Ruiyi Yan, Yating Yang, and Tian Song. 2023. A secure and disambiguating approach for generative linguistic steganography. IEEE Signal Processing Letters, 30:1047–1051. Kuan Yang, Kejiang Chen, Weiming Zhang, and Nenghai Yu. 2019a. Provably secure generative steganography based on autoregressive model. In Digital Forensics and Watermarking, pages 55–68, Cham. Springer International Publishing. Zhong-Liang Yang, Xiao-Qing Guo, Zi-Ming Chen, Yong-Feng Huang, and Yu-Jin Zhang. 2019b. Rnnstega: Linguistic steganography based on recurrent neural networks. IEEE Transactions on Information Forensics and Security, 14(5):1280–1295. Zhong-Liang Yang, Si-Yu Zhang, Yu-Ting Hu, ZhiWen Hu, and Yong-Feng Huang. 2021. Vae-stega: Linguistic steganography based on variational autoencoder. IEEE Transactions on Information Forensics and Security, 16:880–895. Siyu Zhang, Zhongliang Yang, Jinshuai Yang, and Yongfeng Huang. 2021. Provably secure generative linguistic steganography. In Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, pages 3046–3055, Online. Association for Computational Linguistics. Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, Todor Mihaylov, Myle Ott, Sam Shleifer, Kurt Shuster, Daniel Simig, Punit Singh Koura, Anjali Sridhar, Tianlu
Wang, and Luke Zettlemoyer. 2022. OPT: Open pre-trained transformer language models. Preprint, arXiv:2205.01068. Zachary Ziegler, Yuntian Deng, and Alexander Rush. 2019. Neural linguistic steganography. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 1210–1215, Hong Kong, China. Association for Computational Linguistics.
A
Related Work
In this section, we introduce the existing attempts to provably secure steganography, and analyze their characteristics or limitations. A.1
Arithmetic Coding (AC) & Meteor
Arithmetic coding (AC) is a form of entropy encoding used in lossless data compression (Rissanen and Langdon, 1979). A steganographic method that first adopts AC is proposed by Le (2003). Then, AC is applied in deep generative model and image generation to the field of provably secure steganography (Yang et al., 2019a). Following these works, in the field of linguistic steganography, researchers have presented a series of variant methods, especially including the original AC-based steganography (Ziegler et al., 2019), the AC-based method with a self-adjusting mechanism (Shen et al., 2020), and Meteor (Kaptchuk et al., 2021). The sort of these AC-based steganographic methods commonly encounter a problem, that is, the precision limitation results in distortion in the original probability distribution at each generative step. Specifically, when the original probabilities are encoded into binary-based intervals, the selected probability for each token always has the form of (t) 2−p , where p(t) is the precision at time t. It is almost impossible to maintain the original distribution perfectly, thus introducing distortion. To mitigate this distortion, one method is using a higher initial precision, and even Python’s decimal module can be used here to support a precision that is higher than the precision of the tensor. However, during the iteration of AC-based steganography, the external interval is narrowed and expanded many times, and when the external interval is small, p(t) is also small. Therefore, as the precision is AC-based methods are changed all the times and cannot be controlled well, distortion on probability distribution is inevitable.
Besides, even though Meteor addresses some problems that basic AC-based steganography suffers, Meteor suffers from limited embedding capacity. The reason is that, as Meteor does not narrow the interval successively and only considers each generated symbol separately, thus it cannot fully utilize the entropy. And Meteor does not address the probability-distortion problem that arises in AC-based methods.
provably perfect security. However, iMEC does have a certain bit error rate. In addition, to achieve minimum entropy coupling and enhance the embedding rate, a considerable amount of computational complexity, specifically O(|V| log |V|), is necessary to couple the probabilities. Low computation efficiency of iMEC makes it difficult to be practically utilized in a vocabularysize situation.
A.2
A.4
Adaptive Dynamic Grouping (ADG)
Zhang et al. (2021) proposed a grouping-based steganographic method called adaptive dynamic grouping (ADG). At each time step, it dynamically groups the probability distribution of all tokens of the vocabulary into 2r groups with approximately the same probability sum, and then numbers them 0, 1, . . . , 2r − 1. All tokens in each group represent the same message bits of length r. Then, they match the first r bits from the message to be embedded and converts them to a decimal number in {0, 1, . . . , 2r − 1}, and performs random sampling from the normalized distribution of its corresponding group to obtain the next token. In their assumptions, ADG can theoretically achieve perfect security (no probability distortion) if and only if the grouping is perfectly balanced. However, the problem is that since the vocabulary-size probability distribution is discrete, the requirement is almost impossible to satisfy. In most cases, the actual distribution used to embed the message is a modified distribution, which is different from the original distribution. A.3
Iterative Minimum Entropy Coupling (iMEC)
de Witt et al. (2023) analyzed information-theoretic steganography through the lens of minimum entropy coupling. They investigated how much information about a fixed-length secret message can be inferred by the sender and receiver through the selection of tokens, aiming to maximize and accumulate this information until the entire message is determined. They demonstrated that achieving perfect steganographic security is equivalent to solving a coupling problem, and that maximizing transmission efficiency under perfect security corresponds to solving a minimum entropy coupling problem. Their proposed iMEC scheme fully exploits the theoretical properties of coupling and minimum entropy coupling. As a result, the method preserves the original probability distribution and achieves
Distribution Copies (Discop)
Ding et al. (2023) proposed a provably secure steganographic method based on distribution copies (Discop). In this method, several distribution copies are generated by rotating all intervals by specific displacements. At each time step, the message determines which distribution copy to sample from. Discop also employs an iterative method based on the Huffman tree to further enhance the capacity. Experimental results demonstrated a high utilization rate of entropy. However, the complexity of creating a Huffman tree (O(|V|) complexity) at each step could not be efficient when a vocabularysize candidate pool is encoded. Discop works by creating several rotated copies of the model’s probability distribution and picking one copy according to the secret bits. This design must let the receiver uniquely tell which copy is used, without ever changing the model’s original probabilities. In practice, those rotated copies often overlap on the same token: if the random number falls into an overlap (a disputed range), the receiver cannot be sure which copy was chosen. When that happens, the embedding process has to step back and embed fewer bits at that position to keep extraction unambiguous, which directly reduces the per-step payload. These overlaps become more likely whenever one token is much more probable than the rest, because adding more copies pushes more of the token intervals on top of each other. As a result, the achievable rate is effectively governed by the dominance of the most probable token (not by the full entropy of the distribution), and over long texts it only approaches a stricter ceiling rather than the ideal limit. The paper itself notes that, empirically, Discop reaches roughly 92%–95% of its stated theoretical limit because of these disputed ranges and the need to back off to smaller embeddings when they occur. A.5
Sparse Sampling (SparSamp)
Wang et al. (2025) proposed SparSamp, an efficient
and provably secure steganographic method based on sparse sampling. SparSamp embeds messages by combining them with pseudo-random numbers to generate message-derived randomness for sampling. This approach introduces only O(1) additional computational complexity per sampling step, ensuring high computational efficiency. SparSamp embeds bits by turning the random numbers used for sampling into message-driven numbers. If two different message-driven numbers land on the same token, the receiver cannot tell which message was used. The paper calls this an inherent conflict: longer message chunks raise capacity but also raise the chance of such collisions; shorter chunks reduce collisions but waste headroom. To keep extraction unique without changing the distribution, SparSamp deliberately spreads out (sparsifies) the allowable random numbers (i.e., it increases the gap between neighboring positions), so different messages are unlikely to pick the same token. That spacing is the price of uniqueness and inevitably leaves a gap to 100% entropy utilization.
B
Propositions and Proofs
B.1
Proof of Proposition 1 (t)
Proposition 1. ds ∼ U (L(t−1) , R(t−1) ). Proof. Considering Lines 9–10 in Algorithm 3, (t) (t−1) as ds = L(t−1) + (ds − L(t−1) + o(t) × (t−1) (t−1) (t) ∆ ) mod ∆ , and o ∈ U (0, 1), we let (t−1) (t−1) A = ds −L and B = o(t) × ∆(t−1) . Considering X = (A + B) mod ∆(t−1) , for any x ∈ [0, ∆(t−1) ), there is:
B.2
Proof of Proposition 3
Proposition 3. ∆(t) ≤ 1 is a sufficient condition (t) (t) (t) − ds ∈ for the embedding termination L +R 2 (−0.5, 0.5] (Lines 14–15 in Algorithm 3). Proof. If ∆(t) = R(t) − L(t) ≤ 1: (t) L(t) ≤ d(t) ≤ L(t) + 1 s <R
L(t) + R(t) ∈ (L(t) , L(t) +0.5] ⊂ (L(t) , d(t) s +0.5] 2 L(t) + R(t) ∈ [R(t) −0.5, R(t) ) ⊂ (ds −0.5, R(t) ) 2 L(t) + R(t) ∈ (ds − 0.5, ds + 0.5] 2 L(t) + R(t) − d(t) s ∈ (−0.5, 0.5]. 2
B.3
Proof of Computational Security of RRC Steganography
Proposition 4. For all probabilistic polynomial time (PPT) adversary detection AD , |Pr[AD (xs ) = 1] − Pr[AD (xc ) = 1]| < negl(λ) where xs is the stegotext, xc is the normally generated cover text, λ is the security parameter of the shared key K (usually the length of K), and negl(λ) is a negligible function concerning λ.
P (X ≤ x) = P ((A + B) mod ∆(t−1) ≤ x). Let A = k∆(t−1) + r, where k ∈ Z and r ∈ [0, ∆(t−1) ). Considering periodicity of modulo operations, there is
Proof. We prove the computational indistinguishability (security) between stegotext and normal text using a hybrid argument. Define the following hybrid distributions:
(A + B) mod ∆(t−1) = (r + B) mod ∆(t−1) . Case 1: r + B ≤ ∆(t−1) . There are X = r + B (t−1) and P (B ≤ ∆(t−1) − r) = ∆∆(t−1)−r . Case 2: r + B > ∆(t−1) . There are X = r + r B − ∆(t−1) and P (B > ∆(t−1) − r) = ∆(t−1) . (t−1) Therefore, for any x ∈ [0, ∆ ), there is x P (X ≤ x) = (t−1) ∆ which means X ∼ U (0, ∆(t−1) ). (t) (t) As ds = L(t−1) +X, ds ∼ U (L(t−1) , L(t−1) + (t) ∆(t−1) )), thus ds ∼ U (L(t−1) , R(t−1) ).
• Hyb0 – real steganographic generation: using the secret message ms and K. • Hyb1 – modified steganographic generation: (−1) initialized ds as a uniform random value l over [0, 2 ) instead of ms , with other steps unchanged. • Hyb2 – normal generation: sample tokens directly from language model M until the sequence length matches the expected stego length, without interval operations.
Step 1: computational indistinguishability (security) between Hyb0 and Hyb1 (−1)
= bin2dec(ms ).
(−1)
∼ Uniform(0, 2l ).
• In Hyb0 , ds • In Hyb1 , ds
• This factor depends on interval lengths determined by S, which is bounded in [0, 1], and introduces no bias due to language model smoothness. • In computational settings, distinguishers cannot efficiently compute Pr[terminate|S] (requires internal state or LM details), and the factor does not alter core conditional distributions.
(0)
At t = 0, the rotation operation updates ds : (−1) d(0) + o(0) × 2l ) mod 2l . s = (ds
Since o(0) ∼ U (0, 1) implies o(0) × 2l ∼ Uniform(0, 2l ), we have: (−1)
is fixed, ds ∼ Uniform(0, 2l ).
(−1)
(0)
• If ds
(0)
• If ds is uniform, ds still holds.
∼ Uniform(0, 2l )
Crucially, the cryptographically secure PRNG ensures its outputs o(t) are computationally indistinguishable from true randomness. If a valid PPT distinguisher AD exists for Hyb1 and Hyb2 , we build an adversary A′ to break PRNG security: • A′ simulates stego generation but uses a challenge randomness source (PRNG or true random) for o(t) .
(t) ds
For t ≥ 1, ∼ Uniform(L(t−1) , R(t−1) ) which is independent of initialization. Thus, the token sequence distributions of Hyb0 and Hyb1 are identical (statistically indistinguishable). For any PPT distinguisher AD : |Pr[AD (Hyb0 ) = 1] − Pr[AD (Hyb1 ) = 1]| = 0.
• if AD succeeds, A′ breaks PRNG security, which leads to a contradiction against the cryptographically secure PRNG. Thus:
Initialization differences are eliminated by the first rotation step. Step 2: computational indistinguishability (security) between Hyb1 and Hyb2 (−1)
Hyb1 uses random ds and PRNG, but its conditional token distribution matches the normal generation. The stopping time T is stochastic, but:
|Pr[AD (Hyb1 ) = 1] − Pr[AD (Hyb2 ) = 1]| ≤ neglPRNG (λ). Step 3: computational indistinguishability (security) between Hyb0 and Hyb2 By the hybrid argument: |Pr[AD (Hyb0 ) = 1] − Pr[AD (Hyb2 ) = 1]| ≤ |Pr[AD (Hyb0 ) = 1] − Pr[AD (Hyb1 ) = 1]|
• Token distributions conditioned on history match normal generation.
+ |Pr[AD (Hyb1 ) = 1] − Pr[AD (Hyb2 ) = 1]|
• Termination depends on internal uniform vari(t) ables ds and o(t) , which are inaccessible to distinguishers observing only token sequences.
As Hyb0 is real steganographic generation, Hyb2 is normal generation (length-matched), for any PPT distinguisher AD , there is:
Consider Hyb2 (normal generation): Sample tokens stepwise from M for length L = E[T ] (polynomially bounded since T = O(l), efficiently sampleable). For any fixed sequence S = [s(0) , . . . , s(k−1) ], its probability in Hyb1 is: PrHyb1 [S] = Q (t) (t) ( k−1 × Pr[terminate at k|S] × t=0 p (s )) Pr[no early termination|S]. In Hyb (fixed length k): PrHyb2 [S] = Qk−1 (t) 2 (t) t=0 p (s ). Though an extra factor Pr[terminate|S] exists:
≤ 0 + neglPRNG (λ) = neglPRNG (λ).
|Pr[AD (xs ) = 1] − Pr[AD (xc ) = 1]| < negl(λ) where negl(λ) = neglPRNG (λ), which is negligible.
C
Experimental Details & Supplementary Information
C.1
Supplementary Main Results
Tables 4 and 5 report the average results across various metrics for OPT-1.3b and Llama-2-7b. The
Method Multinomial sampling AC ADG Meteor w/o sort Meteor w/ sort iMEC Discop w/o sort Discop w/ sort SparSamp RRC steganography (ours)
Avg / Max KLD ↓ (bits/token) 0/0 1.85E-03 / 1.13E-02 1.38E-04 / 1.61E-03 2.80E-02 / 8.34E-02 2.77E-02 / 8.12E-02 0/0 0/0 0/0 0/0 0/0
Capacity ↑ (bits/token) N/A 4.64 3.45 3.13 3.65 3.24 1.92 4.39 4.35 4.70
Entropy (bits/token) 4.59 4.65 4.64 4.54 4.52 4.61 4.67 4.63 4.53 4.67
Utilization ↑ (%) N/A 99.81 74.20 69.03 80.76 70.24 41.08 94.71 96.08 100.67
Speed ↑ (bits/s) N/A 352.09 25.29 410.79 46.02 19.78 154.25 31.94 852.36 750.41
Table 4: Quantitative comparison with previous steganographic methods on OPT-1.3b.
Method Multinomial sampling AC ADG Meteor w/o sort Meteor w/ sort iMEC Discop w/o sort Discop w/ sort SparSamp RRC steganography (ours)
Avg / Max KLD ↓ (bits/token) 0/0 6.92E-04 / 9.90E-03 1.81E-04 / 3.90E-03 1.24E-02 / 4.00E-02 1.21E-02 / 4.19E-02 0/0 0/0 0/0 0/0 0/0
Capacity ↑ (bits/token) N/A 3.53 2.41 2.42 2.89 2.48 1.50 3.33 3.38 3.57
Entropy (bits/token) 3.46 3.52 3.54 3.50 3.53 3.43 3.49 3.48 3.44 3.52
Utilization ↑ (%) N/A 100.33 68.14 69.14 81.84 72.35 42.99 95.72 98.12 101.41
Speed ↑ (bits/s) N/A 104.37 21.15 98.71 50.26 10.30 127.61 26.13 326.12 146.24
Table 5: Quantitative comparison with previous steganographic methods on Llama-2-7b.
findings are consistent with those in Table 1 (GPT2), where our RRC steganography achieves the highest embedding capacity and embedding utilization among all methods. In contrast, for the two larger language models, our method attains the second-fastest speed, behind SparSamp, which is particularly optimized for efficiency. In addition, some utilization results exceeding 100% appear due to sampling bias from finite data. Similar instances of over-100% utilization have also been reported in recent work (Pan et al., 2025). C.2
Supplementary Results of Scalability
Tables 6 and 7 list the average utilization, speed, and running time when RRC steganography embeds the secret message with various lengths (up to 8192 bits) on OPT-1.3b and Llama-2-7b. Similarly to the results of 2, RRC steganography can achieve steady entropy utilization around 100%. C.3
Supplementary Results of Comparison
Table 8 reports steganalysis accuracies across three steganalysis models, three language models for
steganography, and two steganographic methods (our RRC and the current state-of-the-art baseline, SparSamp). The experimental settings for steganalysis follow the details in Appendix C.4. Table 9 presents the median perplexities under various language models for steganography and two steganographic methods (with multinomial sampling included for reference). The embedded secret message was a random 128-bit sequence, with 1,000 samples per group. Median values are reported because average perplexities are heavily skewed by extreme outliers. Overall, both methods yield near-random steganalysis accuracies (about 50%) and comparable perplexity scores (close to those of multinomial sampling), due to the provable security property shared by RRC steganography and SparSamp. Besides, we emphasize that lower perplexity does not imply higher imperceptibility, due to the conflict between perceptual and statistical imperceptibility (the Psic Effect) in steganography (Yang et al., 2021).
Message length (bits) Utilization (%) ↑ Speed (bits/s) ↑ Running time (s)
32
64
128
256
512
1024
2048
4096
8192
100.09 685.32 0.047
99.26 745.03 0.086
100.67 750.41 0.171
100.35 720.93 0.355
100.30 701.11 0.730
100.02 588.33 1.740
100.14 403.20 5.079
100.14 248.71 16.469
100.08 184.42 44.421
Table 6: Average results on utilization, speed and running time of RRC steganography across various message lengths l on OPT-1.3b. Message length (bits) Utilization (%) ↑ Speed (bits/s) ↑ Running time (s)
32
64
128
256
512
1024
2048
4096
8192
102.01 142.67 0.224
100.29 144.63 0.443
101.41 146.24 1.143
100.52 142.00 1.803
100.25 126.51 4.047
100.31 92.65 11.052
100.35 79.38 25.800
100.17 63.21 64.800
100.04 46.10 177.701
Table 7: Average results on utilization, speed and running time of RRC steganography across various message lengths l on Llama-2-7b.
Steganalysis model bert-base-uncased roberta-base roberta-large
GPT-2 RRC (ours) SparSamp 49.3% 51.1% 48.9%
49.9% 50.5% 49.2%
OPT-1.3b RRC (ours) SparSamp 48.1% 50.1% 52.6%
48.6% 49.7% 51.8%
Llama-2-7b RRC (ours) SparSamp 49.7% 51.3% 47.7%
50.9% 50.5% 47.6%
Table 8: Comparison of steganalysis accuracies against RRC steganography and SparSamp steganography under cases where models for steganography vary and models for steganalysis vary.
Method Multinomial sampling SparSamp RRC steganography (Ours)
GPT-2 81.05 83.56 82.79
OPT-1.3b 74.09 73.18 72.66
Llama-2-7b 74.99 73.37 75.24
Table 9: Comparison of median perplexity between RRC steganography and SparSamp steganography under cases where models for steganography vary.
Method Vanilla RC steganography RRC steganography Vanilla RC steganography RRC steganography Vanilla RC steganography RRC steganography
Avg / Max KLD Capacity Entropy ↓ ↑ (bits/token) (bits/token) (bits/token) Implemented in GPT-2 1.67E-14 / 5.73E-12 5.94 5.93 0/0 5.93 5.93 Implemented in OPT-1.3b 1.46E-14 / 4.13E-12 4.70 4.69 0/0 4.70 4.67 Implemented in Llama-2-7b 7.26E-13 / 1.99E-12 3.55 3.55 0/0 3.57 3.52
Utilization ↑ (%)
Speed ↑ (bits/s)
100.20 99.98
1605.31 1554.66
100.19 100.67
770.49 750.41
99.91 101.41
153.64 146.24
Table 10: Comparison between vanilla RC steganography and RRC steganography in various metrics.
C.4
Steganalysis
We generated 5,000 pairs of cover texts (via multinomial sampling) and steganographic texts, respectively implemented on GPT-2, OPT-1.3b, and Llama-2-7b. In each pair, the lengths (token num-
ber) of two texts are the same. The initial contexts for generation are the first 10 words from sequences randomly selected from the C4 dataset. For each experimental group, 5,000 texts are split in a 6:2:2 ratio to create the training, validation, and test sets.
For fine-tuning BERT or RoBERTa models, we use Adam (Kingma and Ba, 2017) as the optimizer with a learning rate of 5 × 10−5 . The batch size is set to 2048, and the discriminator is trained for 20 epochs, running time of the whole training process is approximately 5 minutes. C.5
Ablation on Rotation Mechanism
To quantify the effect of the rotation mechanism, we implemented a variant without rotation (vanilla RC). As shown in Table 10 (where the experimental setups follow Section 6.1), we can find that, in vanilla RC steganography, even though it can obtain the higher embedding speed compared to RRC steganography, 0 KL divergence cannot be achieved. Most importantly, theoretical security cannot be achieved. Therefore, the provable security of vanilla RC steganography cannot be ensured as shown in the analysis in Section 3.2.
D
Discussion on Practical Issues
One practical issue of linguistic steganography is tokenization inconsistency. The stegotext ts generated by Semb (M, ms ) is essentially a sequence of tokens. Before transmission, the sender must detokenize this sequence using a tokenizer to produce the final stegotext. Consequently, during extraction Sext (M, ts ), any tokenization inconsistency may cause extraction to fail or yield an incorrect secret message. This problem can be avoided only in a few tokenizer-free linguistic steganographic approaches (Xiang et al., 2020; Yan et al., 2024b). Recently, several disambiguation methods have been proposed to mitigate this issue (Nozaki and Murawaki, 2022; Yan et al., 2023, 2024a; Qi et al., 2025; Yan and Murawaki, 2025). These methods are orthogonal to our proposed RRC steganography and can be compatible, since they operate on candidate pools prior to steganographic processing. Another practical issue of linguistic steganography is hardware indeterminism (Atil et al., 2025), whereby LLM outputs and the probability distribution of the next token given the same context can vary across different hardware settings. Such variability poses serious risks for reliable message extraction in real-world deployments, since even small shifts in probability values may result in incorrect extraction. This issue underscores the importance of explicitly addressing hardware-level robustness as an additional design dimension for practical steganographic systems, alongside imper-
ceptibility and capacity, in future research.
E
Samples of Texts
We present examples of stegotexts generated by RRC steganography and non-steganographic texts generated by multinomial sampling. Each stegotext embeds a 128-bit random secret message. The initial context is “Occasionally when I get some free time, I’ll do.” Following the approach of Ziegler et al. (Ziegler et al., 2019), we terminate the generation process once the proposed method has finished embedding the message. In the following examples, for each language model, the non-steganographic text has the same token number as that of the corresponding stegotext.
Texts generated by GPT-2 Stegotext: Occasionally when I get some free time, I’ll do something that uses all of those sensors scanned at the bottom of the computer - search for something. But I don’t know how to do that Non-steganographic text: Occasionally when I get some free time, I’ll do some stretch and the lights rise over me, and will do some real experimenting. I didn’t really think about art where
Texts generated by OPT-1.3b Stegotext: Occasionally when I get some free time, I’ll do flat screen, planner style arrangement cards. It really highlights that the cards are supposed to be focused Non-steganographic text: Occasionally when I get some free time, I’ll do that in survival. It’s loads more fun to just play around and search ways to build a nest and be creative in
Texts generated by Llama-2-7b Stegotext: Occasionally when I get some free time, I’ll do a quick Google search on a random topic that interests me (if I have one free not sitting in front of a computer screen!), and just see where my curiosity takes me. The first thing Non-steganographic text: Occasionally when I get some free time, I’ll do a Google Searche for ""badminton"". It is refreshing not to find the many images that can be found with another more popular global pastime. My experiment of searching finds pictures