arXiv:2604.21394v1 [cs.CR] 23 Apr 2026
Provably Secure Steganography Based on List Decoding Kaiyi Pang
Minhao Bai
Tsinghua University Beijing, China [email protected]
Tsinghua University Beijing, China [email protected]
Abstract
1
Steganography embeds secret messages in seemingly innocuous carriers for covert communication under surveillance. Current Provably Secure Steganography (PSS) schemes based on language models can guarantee computational indistinguishability between the covertext and stegotext. However, achieving high embedding capacity remains a challenge for existing PSS. The inefficient entropy utilization renders them not well-suited for Large Language Models (LLMs), whose inherent low-entropy tendencies severely constrain feasible embedding capacity. To address this, we propose a provably secure steganography scheme with a theoretically proved high capacity. Our scheme is based on the concept of list decoding: it maintains a set of candidates that contain the correct secret message, instead of directly finding the correct message with more effort. This strategy fully utilizes the information content of the generated text, yielding higher capacity. To ensure the correctness of our scheme, we further introduce a suffix-matching mechanism to distinguish the correct secret message from the candidates. We provide theoretical proofs for both the security and correctness of our scheme, alongside a derivation of its theoretical capacity lower bound. Our approach is plug-and-play, requiring only a direct replacement of the model’s standard random sampling module. Experiments on three LLMs and seven PSS baselines demonstrate that our method achieves computational efficiency comparable to prior PSS schemes while delivering a substantial improvement in embedding capacity.
Steganography is a technique for embedding and transmitting private messages within seemingly innocuous carriers such as text [4, 10, 18]. Its primary goal is to conceal not only the content of the secret messages but also the very fact that secret communication is occurring. Provably Secure Steganography (PSS) [8, 10] represents the state-of-the-art paradigm, ensuring that model-generated stegotext is computationally indistinguishable from covertext sampled from the underlying model distribution. As a covert communication mechanism, steganography is required not only to satisfy security guarantees but also to maximize communication efficiency. In the context of provably secure generative text steganography [2, 4, 10], communication efficiency is typically defined as the utilization rate of the entropy of the model distribution. Intuitively, a steganographic scheme with higher capacity can embed more secret messages into shorter stegotext, there-by reducing communication frequency. While non-secure methods [6, 18–20] often boost capacity by distorting the generation distribution, this comes at the unacceptable cost of compromising imperceptibility. In contrast, existing provable secure steganography methods rely primarily on algorithm constructions to improve capacity but often lack principled optimization strategies. Most schemes [4, 10, 11] behave like instantaneous codes, requiring encoded bits to be uniquely decodable immediately after each token is observed. This requirement creates a structural bottleneck. When multiple message candidates map to the same token, an instantaneous encoder must either embed only a short common prefix or forgo embedding at that step altogether. Either choice leaves part of the token’s information content unused, reducing entropy utilization. This limitation is especially problematic for Large Language Models (LLMs), whose next-token distributions are often highly peaked, so many tokens carry little entropy and inherently constrain the embedding capacity. To mitigate this limitation, recent works such as SparSamp [16] and Shimmer [2] explore non-instantaneous approaches and achieve partial capacity gains. However, these methods remain limited: SparSamp lacks a theoretical capacity analysis and stops embedding actively when ambiguity persists, while Shimmer loses information during interval splitting and lacks a mechanism to maintain multiple decoding paths without incurring exponential blowup. More broadly, interval-based representations often require repeated conversions between binary strings and fractional values [2, 16], which can be cumbersome and numerically delicate in practice. Overall, a fundamental gap remains: we need a principled mechanism that continuously exploits entropy by maintaining multiple candidate states within bounded resources, rather than discarding them. Moreover, interval-based representations require frequent conversions
CCS Concepts • Security and privacy → Privacy protections.
Keywords Steganography, Large Language Models, Provable Security, List Decoding ACM Reference Format: Kaiyi Pang and Minhao Bai. 2026. Provably Secure Steganography Based on List Decoding. In Proceedings of Submitted to the Confernence (XXX ’26). ACM, New York, NY, USA, 16 pages. https://doi.org/XXXXXXX.XXXXXXX
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. XXX ’26, 978-1-4503-XXXX-X/18/06 © 2026 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-x-xxxx-xxxx-x/YY/MM https://doi.org/XXXXXXX.XXXXXXX
Introduction
XXX ’26, 978-1-4503-XXXX-X/18/06
between binary strings and fractional values [2, 16], which can be cumbersome in practice. Inspired by list decoding [7, 13] in information theory, we propose a principled steganography scheme that more fully exploits the entropy inherent in the model’s distribution. The basic idea of list decoding is that, when a unique secret message cannot be immediately identified, the decoder instead outputs a compact list of candidates guaranteed to contain the true message. A classic example is the Guruswami–Sudan algorithm [7], which recovers a small list containing the correct codeword even under high error rates. Adapting this paradigm to steganography, our scheme maintains a “list of candidate messages” throughout the generation process. This allows us to defer decoding decisions, thereby avoiding the capacity loss inherent in prior constructions [4, 10, 11] that prioritize immediate unique decoding. In this paper, we introduce a provably secure steganographic scheme grounded in a list-decoding perspective. By strictly following the model’s sampling distribution to expand and filter the candidate list, our method allows the embedding rate to approach the theoretical limit dictated by the entropy of the generated text. Furthermore, to resolve the residual ambiguity inherent in list decoding, we propose a suffix-matching strategy. This mechanism enables the receiver to efficiently identify the unique secret message from the candidate list, ensuring security and correctness while maintaining an embedding capacity near the model’s entropy. The main contributions of this paper are as follows: • We propose a provably secure steganographic scheme based on list decoding, and provide a theoretical analysis showing that its embedding capacity can approach the entropy limit. • We introduce a suffix-matching mechanism to assist in fast and correct decoding, and we provide formal proofs of correctness. • Extensive experiments demonstrate that our method achieves higher capacity than state-of-the-art PSS schemes while preserving comparable computational efficiency and text quality.
2
Related Work
Drawing on the theory of source coding, we classify existing steganographic schemes into instantaneous steganography schemes and non-instantaneous steganography schemes based on according to whether the secret information associated with each stego token can be uniquely decoded upon observing that token. Instantaneous codes require that the secret information can be uniquely determined and decoded each time a token is received; whereas noninstantaneous codes require the receiver to wait for additional tokens before unique decoding.
2.1
Instantaneous steganography schemes
The encoder generates each token independently using a steganographic sampling algorithm, while the decoder applies the corresponding inverse procedure to recover the secret message token by token. In an instantaneous-code scheme, if the sender cannot embed any bits in the current token, it simply skips embedding at that step; the receiver correspondingly detects that no bits were embedded and proceeds to the next token.
Kaiyi Pang and Minhao Bai
2.1.1 METEOR. METEOR [10], proposed by Kaptchuk et al., is the first practical provably secure steganographic scheme for language models. It encrypts the secret bitstream using a key-generated random mask via bitwise XOR, interprets the result as a real number, and embeds it by sampling tokens according to the cumulative distribution function of the language model. The masking process is repeated independently at each generation step, and the common prefix of tokens falling within the range represents the secret information that can be embedded at this time step. Although computationally secure, METEOR does not fully exploit the model’s entropy. Re-randomizing the secret bits at every step truncates the coding process and discards residual entropy, which significantly limits embedding capacity—especially for low-entropy token distributions common in LLMs. To address this issue, a reordering algorithm, METEOR(R.), was later proposed to improve the expected embedding capacity. 2.1.2 DISCOP. Ding et al. proposed a provably secure steganography method based on multiple shifted copies of the model distribution [4]. When distinct random offsets map to different tokens, multiple secret bits can be embedded in a single step, making the scheme an instantaneous code that supports immediate decoding from each generated token. However, substantial overlap among distribution copies severely limits the embedding rate, which is asymptotically bounded by the minimum entropy. To alleviate this limitation, the authors further proposed a Huffman-tree-based variant DISCOP (R.) to improve capacity. 2.1.3 FDPSS. Liao et al. proposed a provably secure steganographic design framework, FDPSS [11], and as an instantiation of this framework, developed a more efficient, capacity-oriented encoding and decoding algorithm. We call this differential-based algorithm GROUP. The encoder first applies a differencing operation to the model’s output distribution and then represents it as a mixture of uniform distributions. During encoding, a random number is sampled to determine which uniform component to draw from, and the secret message is used to select a specific token within the chosen component. This method also belongs to the class of instantaneous codes, as both encoding and decoding depend only on the distribution at the current time step.
2.2
Non-instantaneous decode steganography schemes
The construction of decoding algorithms for non-instantaneous codes is more complex compared with instantaneous algorithms. The steganographic encoder must generate multiple tokens consecutively using a steganographic sampling algorithm, progressively narrowing the range of possible secret messages until the message is uniquely determined. The decoder mirrors this range-narrowing process of the encoder and continues until the secret message can be accurately recovered. 2.2.1 Shimmer. To address the inefficiency of METEOR [10], Bai et al. proposed Shimmer [2], a provably secure steganographic scheme that incorporates an entropy-collection mechanism. Its security relies on the indistinguishability between 𝑟 ∼ Unif [0, 1) and 𝑟 + 𝐵 mod 1 ∼ Unif [0, 1), where 𝐵 denotes the fractional representation of the secret message. During encoding, the sampler adds 𝐵
Provably Secure Steganography Based on List Decoding
to the random variable 𝑟 and applies inverse transform sampling to generate tokens; the interval shift enables recovery of the secret interval. By progressively merging intervals across steps, Shimmer embeds the secret message while mitigating interval splitting through additional mechanisms. Overall, Shimmer achieves high entropy utilization with computational security, representing an early transition from instantaneous to non-instantaneous coding. 2.2.2 SparSamp. To address both the capacity and efficiency limitations of DISCOP [4], Wang et al. proposed SparSamp [16], a provably secure steganographic scheme that improves decoding accuracy by inserting gaps between sampling intervals without additional time complexity. From a non-instantaneous coding perspective, SparSamp encodes a fixed-length 𝐿-bit secret by generating 2𝐿 samples and repeatedly filtering candidate messages across multiple steps until only the true secret remains. While SparSamp achieves state-of-the-art embedding capacity, it lacks a formal capacity proof, and its fixed-length design still underutilizes joint entropy, leaving room for further improvement.
XXX ’26, 978-1-4503-XXXX-X/18/06
description of the scheme, including all public hyperparameters that determine the covertext channel (e.g., the language model and tokenizer). The only secret information withheld from the warden is the shared key 𝑠𝑘. The warden is given oracle access either to the stego encoder Enc𝑠𝑘,Model (·, ·) or to the model sampler Model(·), and try to distinguish between the two. Security definition. We define the security of steganographic system against chosen hiddentext attacks [8, 10]. Intuitively, ΣModel is secure if no probabilistic polynomial-time (PPT) adversary can distinguish, with non-negligible advantage, between access to Enc𝑠𝑘,Model (·, ·) and access to the model sampler Model(·), given outputs of the same length. More formally, Definition 3 (Security). A steganography scheme ΣModel is secure if for any probabilistic polynomial-time adversary A, he cannot effectively distinguish the stegotext generated by Enc and the covertext generated by Model. | Pr[A Enc𝑠𝑘,Model (·,·) (1𝜆 ) = 1] − Pr[A Model(·) (1𝜆 ) = 1] | (2)
3 Method 3.1 Prelimilary Following the notion of Hopper [8] and Kaptchuk [10], we formally define steganography scheme as follows: Definition 1 (Steganography scheme). A steganography scheme ΣD on a covertext distribution D is a triple of (probabilistic) algorithms (KeyGen, Enc𝑠𝑘,D, Dec𝑠𝑘,D ). • KeyGen(1𝜆 ) is a randomized algorithm that takes an arbitrary input of length 𝜆 and generates the key 𝑠𝑘 shared between the sender and receiver. • Enc𝑠𝑘,D (𝑚, ℎ) is a keyed randomized algorithm that takes as input a secret message 𝑚 ∈ {0, 1}∗ and the history ℎ and outputs a stegotext 𝑡. • Dec𝑠𝑘,D (𝑡, ℎ) is a keyed randomized algorithm that takes as input the stegotext 𝑡 and the history ℎ and outputs the secret message 𝑚. In this paper, we mainly use the language models to obtain the covertext distribution D. So the encoding and decoding algorithms can be written as Enc𝑠𝑘,Model (𝑚, ℎ) and Dec𝑠𝑘,Model (𝑡, ℎ) Basically, a useful steganography scheme ΣModel should satisfy correctness and security. Í Definition 2 (Correctness). A steganography scheme Model is correct if for any history ℎ and any message 𝑚, the stegotext generated by Enc𝑠𝑘,Model (𝑚, ℎ) should be correctly decoded by the decoding algorithm only with negligible probability of error. Pr[Dec𝑠𝑘,Model (Enc𝑠𝑘,Model (𝑚, ℎ), ℎ) = 𝑚] (1) ≥ 1 − negl(𝜆), where negl(𝜆) is the negligible function that correlates to the secure parameter 𝜆. Threat model. We consider a probabilistic polynomial-time (PPT) warden (adversary) who monitors the communication channel and attempts to determine whether an observed message is a stegotext or an innocent covertext. Following the standard chosen-hiddentext attack (CHA) setting [8, 10], the warden knows the full public
≤ negl(𝜆). Here the 1𝜆 represents the internal randomness of adversary A, and A outputs 1 if he recognizes the output of Enc or Model as stegotext. Access assumptions. Our construction assumes a symmetric setting in which both the sender and the receiver can access the full conditional next-token distribution 𝐷 = Model(ℎ) for any history ℎ. Such access is required to perform alias sampling and to synchronize the message-to-token mapping between the two parties. Pure black-box settings and other asymmetric scenarios(such as the sender and receiver have the different ) are beyond the scope of this work. Useful inequalities. The following two classical inequalities are used frequently in our analysis. Lemma 1 (Hoeffding’s inequality). 𝑋 1, 𝑋 2, · · ·, 𝑋𝑛 are independent and identical random variables, and each 𝑋𝑖 is bounded by [𝑙, ℎ]. Í Let 𝑋 = 𝑛1 𝑛𝑖=1 𝑋𝑖 and 𝜇 = E[𝑋 ], the probability that the sample mean 𝑋 deviates from the theoretical mean E[𝑋 ] up to 𝑡 is 2𝑛𝑡 2 P (|𝑋 − 𝜇| ≥ 𝑡) ≤ 2 exp − . (3) (ℎ − 𝑙) 2 Lemma 2 (Cauchy-Schwarz inequality). For any real sequences {𝑎𝑖 }𝑙𝑖=1 and {𝑏𝑖 }𝑙𝑖=1 , the square of the sum of their pairwise products is bounded by the product of the sums of their squares: !2 ! 𝑙 ! 𝑙 𝑙 ∑︁ ∑︁ ∑︁ 2 2 𝑎𝑖 𝑏 𝑖 ≤ 𝑎𝑖 𝑏𝑖 . (4) 𝑖=1
𝑖=1
𝑖=1
In the special case where 𝑎𝑖 = 1 for all 𝑖, the inequality simplifies to: !2 𝑙 𝑙 ∑︁ ∑︁ 𝑏𝑖 ≤ 𝑙 𝑏𝑖2 . (5) 𝑖=1
3.2
𝑖=1
Our Steganography Scheme
3.2.1 Intuition. As discussed in prior section 2, existing provably secure steganography typically relies on instantaneous codes, where the receiver must be able to uniquely decode bits at the exact moment a token is received. This limitation often forces the sender
XXX ’26, 978-1-4503-XXXX-X/18/06
Kaiyi Pang and Minhao Bai
Stegotext
Auto-Regressive Prompt
Secret Prefix
=11011....110101
Model Sample
=11011....110101
......
Model Sample
Receiver
Sender =11011....110101
000
b
00100
b
001
a
00101
a
010
b
00110
a
011
c
00111
b
100
c
11000
b
101
c
11001
a
110
a
11010
b
suffix
111
b
11011
c
Ensure correct decoding
Initialized Candidate List
Output a token 001 110
Candidate List
Sample List
Suffix Matching Output c token
11011...000 11011...010 11011...011
11011
......
Filter
Map
101
11011...100
Augmented Candidate List
Expand
11011...100
match?
11011...101
...... Map
......
Unique Decoded Message corresponding Stegotext
Filter
Figure 1: Toy illustration to our embedding process. The prefix of the secret message 𝑚 defines an initial candidate list 𝑀0 . After mapping through the language model to obtain 𝑆, candidates whose prefixes correspond to the same tokens in 𝑆 are retained, forming the filtered set 𝑀1 , and the token 𝑠 1 associated with the secret message is selected for output. Autoregressive generation proceeds in this manner until both the secret message and its suffix are fully embedded. Finally, suffix matching is applied to the filtered candidate list 𝑀𝑡 , enabling rapid elimination of non-secret candidates and guaranteeing unique decodability of the secret message from the stegotext. to skip embedding at certain steps to avoid ambiguity, resulting in suboptimal capacity usage. To overcome this, we look to list decoding [7, 13] for inspiration. Fundamentally, list decoding relaxes the constraint of outputting a single message, allowing the algorithm to produce a list of possibilities, one of which is the correct message. Inspired by list decoding, our proposed scheme does not require the receiver to uniquely decode the secret at the immediate token level. Instead, we allow the secret information to be embedded continuously at every time step, even if immediate extraction is ambiguous, aiming to maximize the utilization of the generative distribution’s entropy and expand steganographic capacity. The correct secret message persists within a set of surviving candidates across time steps, while incorrect candidates (those conflicting with the secret) are naturally "filtered" out during the sequential token selection process. To ensure correctness, we introduce a suffix matching mechanism. The combination of this natural filtering and suffix matching theoretically guarantees that the receiver can uniquely recover the message after observing the complete stegotext (theoretical proofs regarding correctness are detailed in Section 3.3). Figure 1 also illustrates an example of this encoding process.
3.2.2 Codec. The workflow of the encoding and decoding algorithm can be summarized by a four-step process: "Mapping, Filtering, Expanding, and Matching". Mapping. During the sampling process, the sender must generate a number of samples equal to the number of candidate secret messages in the current candidate list. To share these samples between the sender and receiver, a pseudorandom generator is employed to generate all random numbers used during the sampling process. To effectively gather a sufficient quantity of samples for establishing a direct mapping between secret messages and samples, some fast sampling techniques such as the Alias sampling method [14, 15], detailed in Appendix A.1, can be employed. Assuming the list of candidate secret messages at a certain step is 𝑀, |𝑀 | we generate |𝑀 | samples {𝑠𝑖 }𝑖=1 to construct the sample list 𝑆 by the codebook mapping 𝐹 (𝑚𝑖 ) := 𝑠𝑖 , 𝑚𝑖 ∈ 𝑀. Subsequently, based on the current prefix of the embedded bitstring (secret bits together with the validation suffix), denoted 𝑚 1:𝑙 , the sample 𝑠 ∗ = 𝐹 (𝑚 1:𝑙 ) is output. Since the generated samples are mutually independent, randomly selecting and outputting one is equivalent to the model’s normal sampling process (detail is provided in the security proof section 3.4).
Provably Secure Steganography Based on List Decoding
XXX ’26, 978-1-4503-XXXX-X/18/06
Filtering. Transmitting a single sample 𝑠 ∗ does not uniquely determine the secret message because multiple different candidate messages may map to the same sample; that is, the pre-image set 𝐹 −1 (𝑠 ∗ ) = {𝑚𝑖 : 𝐹 (𝑚𝑖 ) = 𝑠 ∗ } may contain multiple elements. We can view the embedding process as a filtering process that progressively eliminates candidate messages. At the start of embedding, the sender initializes a candidate list 𝑀0 containing all possible 𝑁 -bit strings, with a size of 2𝑁 . Clearly, the 𝑁 -bit prefix of the real secret message 𝑚 ∗1:𝑁 is in 𝑀0 . The sender then constructs the Sample List 𝑆 by message-to-token mapping 𝐹 1 , and sends the sample 𝑠 1∗ = 𝐹 1 (𝑚 ∗1:𝑁 ). Upon receiving 𝑠 1∗ , the receiver identifies all candidates capable of producing this sample using the inverse mapping, which is the pre-image set of 𝑠 ∗ : 𝑀1 = 𝐹 1−1 (𝑠 ∗ ). At this point, the prefix 𝑚 ∗1:𝑁 must also belong to 𝑀1 . Since the pre-image set 𝑀1 is a subset of 𝑀0 , we have |𝑀1 | ≤ |𝑀0 |, narrowing the candidate list. Further analysis reveals the probability and extent of this list reduction. Assuming the output token is 𝑠 with probability 𝐷 (𝑠), and we draw |𝑀0 | i.i.d. samples to construct the mapping, on average, a proportion of 𝐷 (𝑠) of the candidate messages remains, i.e., E [|𝑀1 |] = 𝐷 (𝑠) · |𝑀0 |. According to Hoeffding’s inequality, the |𝑀1 | upper bound of the ratio |𝑀 is given by: 0| |𝑀1 | ≥ 𝐷 (𝑠) + 𝛿 ≤ exp −2𝛿 2 |𝑀0 | . (6) Pr |𝑀0 | Therefore, determining a sufficiently large 𝑀0 guarantees the elimination of a (1 − 𝐷 (𝑠)) proportion of candidates. For instance, when |𝑀0 | = 220 , the deviation 𝛿 rarely exceeds 0.5%. In practical applications, the number of samples should be maximized without affecting the execution time, and a very large candidate list should be maintained at each step to ensure filtering efficiency. From an information-theoretic perspective, although the secret message is not uniquely determined at this stage, the possible choices are reduced. for the decoder, the entropy of the secret message drops from log2 (|𝑀0 |) to log2 (|𝑀1 |), a reduction of |𝑀0 | ≈ log2 (𝐷 (𝑡)). This approximates the information of the log2 |𝑀 1| token. Expanding After filtering, the size of the candidate list decreases. To embed more secret bits and maintain the candidate list size at a high level, the list should be expanded. A feasible strategy is as follows: for each candidate message 𝑚 in the current list 𝑀𝑖 , append bits ‘0’ and ‘1’ to generate two new messages 𝑚∥0 and 𝑚∥1. These form the augmented list 𝑀𝑛′ . Clearly, if the 𝑘-bit prefix 𝑚 ∗1:𝑘 belongs to 𝑀𝑖 , then the (𝑘 + 1)-bit prefix 𝑚 ∗1:𝑘+1 belongs to 𝑀𝑖′ . To prevent memory overflow from exponential growth, an upper limit 2𝑁 (e.g., 220 ) is set. If the expanded list size is still less than half of the limit (2𝑁 −1 ), the expansion operation repeats until the size exceeds 2𝑁 −1 . Consequently, the filtering step is always performed with more than 2𝑁 −1 candidate messages, effectively ensuring that the entropy dissipated in each step remains low. The complete filtering-expanding process can be viewed as follows: Filter
Filter
Expand 𝑒 1 times
Filter
Algorithm 1 Enc𝑠𝑘,Model,2𝑁 (ℎ, 𝑚 ∗ ) → − 𝑡 Input: Secret key 𝑠𝑘, Language Model Model, History ℎ, Secret message 𝑚 ∗ , Maximum list length 2𝑁 ; Output: Stegotext 𝑡. 1: 𝑀, 𝑡 ←− {0, 1} 𝑁 , ∅ {Initialize candidate message list 𝑀 and stegotext 𝑡} 2: 𝑙, 𝑐𝑛𝑡 ←− 𝑁 , 0 {Initialize message-length counter 𝑙 and counter 𝑐𝑛𝑡} 3: 𝑠𝑢 𝑓 ←− PRG𝑠𝑘 (·) {Shared validation suffix} 4: 𝑚 ←− 𝑚 ∗ ∥𝑠𝑢 𝑓 {Add suffix} 5: while 𝑙 ≤ |𝑚| do 6: 𝑐𝑛𝑡 ←− 𝑐𝑛𝑡 + 1 7: 𝐷 ←− Model(ℎ) {Obtain distribution} 2|𝑀 | 8: {𝑟𝑖 }𝑖=1 ←− PRG𝑠𝑘 (·) {Derive pseudorandomness}
|𝑀 | 2|𝑀 | {𝑠𝑖 }𝑖=1 ←− AliSample |𝑀 | 𝐷, {𝑟 }𝑖=1 {Execute Alias sampling to obtain |𝑀 | samples} 10: for 𝑖 = 1 to |𝑀 | do 11: Let 𝐹 (𝑚𝑖 ) := 𝑠𝑖 {Construct a mapping} 12: end for 13: 𝑠 ∗ ←− 𝐹 (𝑚 1:𝑙 ) {Select token corresponding to current message prefix} 14: 𝑡, ℎ ←− 𝑡 ∥𝑠 ∗, ℎ∥𝑠 ∗ {Append new token 𝑠 ∗ to stegotext and history} 15: 𝑀 ←− 𝐹 −1 (𝑠 ∗ ) {Find pre-image set of 𝑠 ∗ and update candidate message list 𝑀} 16: while |𝑀 | ≤ 2𝑁 −1 do 17: 𝑀 ←− {𝑚∥𝑏𝑖𝑡 : 𝑚 ∈ 𝑀, 𝑏𝑖𝑡 ∈ {0, 1}} {Expand candidate message list 𝑀} 18: 𝑙 ←− 𝑙 + 1 {Increment candidate message length after expansion} 19: end while 20: end while 21: return 𝑡
9:
secret message 𝑚 ∗ . To ensure the receiver can uniquely determine 𝑚 ∗ , a validation phase is appended. Concretely, the sender and receiver derive a pseudorandom validation suffix 𝑠𝑢 𝑓 from the shared key, append it to the payload, and continue embedding. Since the suffix is pseudorandom and sufficiently long (detailed analysis in Section 3.3), with high probability only the candidate corresponding to the real payload will fully match it, enabling unique decoding. The decoding algorithm is essentially the symmetric inverse of the encoding process. Detailed procedures for the encoding algorithm, Enc𝑠𝑘,Model,2𝑁 (ℎ, 𝑚 ∗ ), and the decoding algorithm, Dec𝑠𝑘,Model,2𝑁 (ℎ, 𝑡, |𝑚 ∗ |), are presented in Algorithm 1 and Algorithm 2, respectively. To account for potential hardware constraints, we denote the maximum candidate list length, which also serves as the maximum sample count, as the subscript parameter 2𝑁 .
Filter
𝑀0 −−−−→ · · · −−−−→ 𝑀𝑖 −−−−−−−−−−−−→ 𝑀𝑖′ −−−−→ 𝑀𝑖+1 −−−−→ · · · Matching The "Filter-Expand" process repeats until all bits of the secret message are embedded. At this stage, the candidate list 𝑀𝑛 still contains multiple messages, one of which is the complete real
3.3
Proof of Correctness
We now verify the condition under which the probability of nonunique decoding is negligible.
XXX ’26, 978-1-4503-XXXX-X/18/06
Kaiyi Pang and Minhao Bai
Algorithm 2 Dec𝑠𝑘,Model,2𝑁 (ℎ, 𝑡, |𝑚 ∗ |) → − 𝑚∗ Input: Secret key 𝑠𝑘, Language Model Model, History ℎ, Stegotext 𝑡, Payload length |𝑚 ∗ |, Maximum list length 2𝑁 ; Output: Recovered secret message 𝑚 ∗ . 1: 𝑀 ←− {0, 1} 𝑁 {Initialize candidate message list} 2: 𝑙, 𝑐𝑛𝑡 ←− 𝑁 , 0 {Initialize counters} 3: 𝑠𝑢 𝑓 ←− PRG𝑠𝑘 (·) {Reconstruct shared validation suffix} 4: while 𝑙 ≤ |𝑚 ∗ | + |𝑠𝑢 𝑓 | do 5: 𝑐𝑛𝑡 ←− 𝑐𝑛𝑡 + 1 6: 𝐷 ←− Model(ℎ) {Obtain distribution} 2|𝑀 | 7: {𝑟𝑖 }𝑖=1 ←− PRG𝑠𝑘 (·) {Reconstruct randomness}
|𝑀 | 2|𝑀 | {𝑠𝑖 }𝑖=1 ←− AliSample |𝑀 | 𝐷, {𝑟 }𝑖=1 {Alias sampling} 9: for 𝑖 = 1 to |𝑀 | do 10: Let 𝐹 (𝑚𝑖 ) := 𝑠𝑖 {Reconstruct mapping 𝐹 } 11: end for 12: ℎ ←− ℎ∥𝑡𝑐𝑛𝑡 {Autoregressive update of history} 13: 𝑀 ←− 𝐹 −1 (𝑡𝑐𝑛𝑡 ) {Filter candidates by observed token} 14: while |𝑀 | ≤ 2𝑁 −1 do 15: 𝑀 ←− {𝑚∥𝑏𝑖𝑡 : 𝑚 ∈ 𝑀, 𝑏𝑖𝑡 ∈ {0, 1}} {Expand candidate list} 16: 𝑙 ←− 𝑙 + 1 17: end while 18: end while 19: Find the unique 𝑚 ∈ 𝑀 such that 𝑚 |𝑚 | − |𝑠𝑢 𝑓 |:|𝑚 | = 𝑠𝑢 𝑓 20: Output 𝑚 ∗ ←− 𝑚 1:|𝑚 ∗ | {Drop validation suffix} 21: return 𝑚 ∗
8:
Since 𝑛 ∑︁ 𝑘=1
𝛿𝑘 ·
∑︁
Ö
𝐷 (𝑠 𝑗 ) ≥
𝑛 ∑︁ 𝑛
𝛿𝑘
𝑛 Ö
𝐷 (𝑠 𝑗 )
𝑘
𝑆 ⊆ {1,...,𝑛} 𝑗 ∈𝑆 |𝑆 |=𝑘
𝑘=1
𝑗=1
= ((1 + 𝛿)𝑛 − 1)
𝑛 Ö
𝐷 (𝑠𝑖 ),
(10)
𝑖=1
combining this with Eq. 9, we obtain: (1 + 𝛿)𝑛
𝑛 Ö
𝐷 (𝑠𝑖 ) ≤ 2−𝑏 .
(11)
𝑖=1
Here we computes the maximum value of 𝛿: as the maximum candidate list size is 2𝑁 , we know that |𝑀1 | ≥ 2𝑁 −1 . By Hoeffding √︃ in equality, ensuring exp −2𝛿 2 · 2𝑁 −1 ≤ exp (−𝜆) yields 𝛿 ≤ 2𝜆𝑁 . Using the conclusion of Eq. 11: Pr [𝑚∥𝑠𝑢 𝑓 appears | 𝑚 exists] = ≤
2−𝑏 ≤ (1 + 𝛿)𝑛
𝑛 Ö
𝐷 (𝑠𝑖 )
𝑖=1 2−𝑏
1+
√︃
𝜆 2𝑁
𝑛 .
(12)
By letting the right-hand side be less than exp(−𝜆), we maintain a negligible probability of collision when the suffix length 𝑏 satisfies: & √︂ !' 𝜆 . (13) 𝑏 ≥ 𝜆 log2 𝑒 + 𝑛 log2 1 + 2𝑁 □
Proposition 1. For any non-secret message element 𝑚 in the candidate list, if the validation suffix 𝑠𝑢 𝑓 ∈ {0, 1}𝑏 is uniformly random (or pseudorandomly generated via PRG𝑠𝑘 ) and the maximum candidate list size is 2𝑁 , the probability that 𝑚∥𝑠𝑢 𝑓 appears in the −𝑏 subsequent candidate list is at most √︃2 𝜆 𝑛 , where 𝑛 is the number 1+
2𝑁
of tokens added to embed 𝑠𝑢 𝑓 . Proof. Let the additional generated token sequence of suffix be 𝑠 1, 𝑠 2, · · · , 𝑠𝑛 . In each step, the probability that an element 𝑚 in the candidate list is retained during filtering is 𝐷 (𝑠 𝑗 ). Given that 𝑚 exists in the candidate list, the probability of 𝑚∥𝑠𝑢 𝑓 appearing is: Pr [𝑚∥𝑠𝑢 𝑓 appears | 𝑚 has appeared] =
𝑛 Ö
𝐷 (𝑠 𝑗 ).
(7)
𝑖=1
Since the candidate list expanded 𝑏 times during this process, we have: 𝑛 Ö (𝐷 (𝑠𝑖 ) + 𝛿) ≤ 2−𝑏 , (8) 𝑖=1
where 𝛿 is the deviation from the Hoeffding inequality. Equation 8 can be expanded as: 𝑛 Ö 𝑖=1
(𝐷 (𝑠𝑖 ) + 𝛿) =
𝑛 Ö 𝑖=1
𝐷 (𝑠𝑖 ) +
𝑛 ∑︁ 𝑘=1
𝛿𝑘 ·
∑︁
Ö
𝑆 ⊆ {1,...,𝑛} 𝑗 ∈𝑆 |𝑆 |=𝑘
𝐷 (𝑠 𝑗 ) ≤ 2−𝑏 . (9)
That is, when the suffix 𝑠𝑢 𝑓 has length 𝑏, the probability that 𝑚∥𝑠𝑢 𝑓 appears in the subsequent candidate-message set is at most 2 −𝑏 √︃ 𝑛 , where 𝑛 is the additional number of tokens generated 𝜆 1+
2𝑁
in √︃ m if the suffix 𝑠𝑢 𝑓 has length at least l this process. Equivalently, 𝜆 log2 𝑒 + 𝑛 log2 1 + 2𝜆𝑁 , then the probability that 𝑚∥𝑠𝑢 𝑓 appears in the subsequent candidate-message set is negligible.
3.4
Proof of Security
To prove the security of the proposed scheme, we construct the following sequence of games: • 𝐺 0 : The steganography encoding algorithm Encode𝑠𝑘,Model,2𝑁 (ℎ, 𝑚 ∗ ) using key-controlled pseudorandom numbers; • 𝐺 1 : EncodeModel,2𝑁 (ℎ, 𝑚 ∗ ) using truly random numbers; • 𝐺 2 : EncodeModel,2𝑁 (ℎ) using truly random numbers, with the secret message 𝑚 ∗ omitted; • 𝐺 3 : EncodeModel,1 (ℎ) using truly random numbers to draw a single sample via alias sampling, with the secret message 𝑚 ∗ omitted. The detailed procedure of AliSample is given in Appendix A.1; We illustrate the games involved in the hybrid proof in Figure 2. We can prove the following proposition: Proposition 2. For any history ℎ, message 𝑚 ∗ , secret key 𝑠𝑘 generated by KeyGen, the distribution of the stegotext generated by the encoding algorithm Enc𝑠𝑘,Model,2𝑁 (ℎ, 𝑚 ∗ ) is computationally indistinguishable from the distribution of covertext generated by Model(ℎ).
Provably Secure Steganography Based on List Decoding
XXX ’26, 978-1-4503-XXXX-X/18/06 2|𝑀 | • Input a pseudorandom number sequence {𝑟 }𝑖=1 and a true 2|𝑀 | ′ random number sequence {𝑟 }𝑖=1 ; 2|𝑀 | 2|𝑀 | and {𝑟 ′ }𝑖=1 as the randomness, • A ′ runs 𝐺 0 using {𝑟 }𝑖=1 respectively, to obtain outputs 𝑠 and 𝑠 ′ ; • A ′ invokes the adversary A to distinguish between 𝑠 and 𝑠′.
𝐺 0 : Steganographic Encoding Algorithm 1: 𝐷 ←− Model(ℎ){Obtain distribution} 2|𝑀 |
←− PRG𝑠𝑘 (·){Generate pseudorandom numbers} |𝑀 | 2|𝑀 | 3: {𝑠𝑖 }𝑖=1 ←− AliSample |𝑀 | 𝐷, {𝑟 }𝑖=1 {Alias sampling} 4: for 𝑖 = 1 to |𝑀 | do 5: Let 𝐹 (𝑚𝑖 ) := 𝑠𝑖 {Construct mapping 𝐹 } 6: end for 7: return 𝐹 (𝑚 ∗1:𝑙 ) {Select sample 𝑠 ∗ corresponding to the real secret message} 2: {𝑟 }𝑖=1
𝐺 1 : Using True Random Number 1: 𝐷 ←− Model(ℎ){Obtain distribution} 2|𝑀 |
2: {𝑟 }𝑖=1
|𝑀 |
3: {𝑠𝑖 }𝑖=1
←−$ Unif [0, 1]{Get true random numbers} 2|𝑀 | ←− AliSample |𝑀 | 𝐷, {𝑟 }𝑖=1
{Alias sam-
pling} 4: for 𝑖 = 1 to |𝑀 | do 5:
Let 𝐹 (𝑚𝑖 ) := 𝑠𝑖 {Construct mapping 𝐹 }
6: end for 7: return 𝐹 (𝑚 ∗1:𝑙 ) {Select sample 𝑠 ∗ corresponding to the
real secret message}
𝐺 2 : Removing Secret Message 1: 𝐷 ←− Model(ℎ){Obtain distribution} 2|𝑀 |
2: {𝑟 }𝑖=1
|𝑀 | 3: {𝑠𝑖 }𝑖=1
←−$ Unif [0, 1]{Get true random numbers} 2|𝑀 | ←− AliSample |𝑀 | 𝐷, {𝑟 }𝑖=1
{Alias sampling} 4: Choose 𝑖 ←−$ {1, . . . , |𝑀 |} {Uniformly select one of the samples} 5: 𝑠 ∗ ←− 𝑠𝑖 6: return 𝑠 ∗
𝐺 3 : Normal Model Sampling 1: 𝐷 ←− Model(ℎ){Obtain distribution} 2 ←− Unif [0, 1]{Get true random numbers} 2: {𝑟 }𝑖=1 $
3: 𝑠 ∗ ←− AliSample1
2 𝐷, {𝑟 }𝑖=1 {Alias sampling}
4: return 𝑠 ∗
Figure 2: The games used in security proof. Proof. 𝐺 0 ≈ 𝐺 1 : Assume there exists a polynomial-time adversary A capable of effectively distinguishing the output of 𝐺 0 from that of 𝐺 1 . We can then construct another polynomial-time adversary A ′ that can effectively distinguish between a true random number sequence and a pseudorandom number sequence. The workflow of A ′ is as follows:
Since the 𝐺 0 algorithm using true random numbers is essentially identical to 𝐺 1 , 𝑠 and 𝑠 ′ correspond to the outputs of 𝐺 0 and 𝐺 1 under the same history ℎ and secret message 𝑚 ∗ , respectively. Thus, they can be effectively distinguished by the adversary A. Consequently, A ′ can further distinguish the true random number sequence from the pseudorandom number sequence by invoking A. However, by the definition of pseudorandom property, such an adversary A ′ does not exist. An adversary capable of distinguishing between algorithms 𝐺 0 and 𝐺 1 must necessarily be able to distinguish between true and pseudorandom sequences; therefore, such an adversary cannot operate in polynomial time. Since there is no polynomialtime adversary that can effectively distinguish between 𝐺 0 and 𝐺 1 , by the definition of computational indistinguishability, the outputs of 𝐺 0 and 𝐺 1 are computationally indistinguishable. 𝐺 1 = 𝐺 2 : In 𝐺 1 , the encoder outputs 𝑠 ∗ = 𝐹 (𝑚 ∗1:𝑙 ), where 𝐹 is constructed by drawing i.i.d. samples from 𝐷 = Model(ℎ) using true randomness. Therefore 𝑠 ∗ is distributed exactly as a fresh sample from 𝐷, i.e., for any token 𝑠, Pr[𝑠 ← 𝐺 1 (ℎ, 𝑚 ∗ )] = 𝐷 (𝑠). In 𝐺 2 , the encoder instead chooses a uniformly random element from the same multiset of i.i.d. samples; by symmetry, the output distribution is also 𝐷. Hence 𝐺 1 and 𝐺 2 are identically distributed. 𝐺 2 = 𝐺 3 : 𝐺 2 randomly selects one element from the multiset of |𝑀 | i.i.d. samples, while 𝐺 3 draws a single fresh sample from the distribution. It was proven in the previous step that the probability of 𝐺 2 outputting token 𝑠 is 𝐷 (𝑠), following the distribution predicted by the model. Since 𝐺 3 utilizes alias sampling, the output of this sampling algorithm must follow the given input distribution 𝐷; thus, the probability of it outputting token 𝑠 remains 𝐷 (𝑠). In summary, we have established that 𝐺 0 ≈ 𝐺 1 = 𝐺 2 = 𝐺 3 . This demonstrates that the output of our steganographic encoding algorithm is computationally indistinguishable from the model’s normal output at any single generation step. By the autoregressive nature of the generation process and the chain rule, it follows that the full text sequences generated by Enc𝑠𝑘,Model,2𝑁 (ℎ, 𝑚) and Model(ℎ) are computationally indistinguishable. □
3.5
Capacity Analysis
First, we define the embedding capacity within the steganographic scheme. In common instantaneous decoding steganography schemes, capacity is typically defined as the average ratio of the number of bits that can be embedded and accurately extracted per token to the information of that token, which can be viewed as the information utilization rate. As our steganography scheme cannot decode any bit from a single token, the information utilization rate can be defined as follows: Definition 4 (Information Utilization Rate of steganographic scheme). Let the generated stegotext be a token sequence 𝑠 1, 𝑠 2, · · · , 𝑠𝑛all . For each step 𝑖, let 𝑝𝑖 = Pr[𝑠𝑖 | ℎ <𝑖 ] = Model(ℎ <𝑖 ) (𝑠𝑖 )
XXX ’26, 978-1-4503-XXXX-X/18/06
Kaiyi Pang and Minhao Bai
be the conditional probability assigned by the cover distribution. The total information content of the stegotext is 𝐼=
𝑛 all ∑︁
− log2 (𝑝𝑖 ).
Í𝑛all
𝑖=1 1
2 · 𝛿 2 and applying the Cauchy-Schwarz inequality, we have: 𝑖 𝑛 all ∑︁
(14)
!2 1 · 𝛿𝑖
≤
𝑖=1
𝑖=1
𝑖=1
Í𝑛all
𝑛 all ∑︁
! 12
𝑛 all ∑︁
! 𝛿2 ≤
𝑛 2all 𝜆 .
(20)
2𝑁
𝑖=1
√︃
𝜆 . Denoting the total information 2𝑁 Í𝑛all content of tokens 𝑠 1, 𝑠 2, · · · 𝑠𝑛all as 𝐼 = 𝑖=1 − log2 (𝑝𝑖 ), the lower
≤ 𝑛 all
Let |𝑚 ∗ | denote the payload length (excluding the validation suffix). The information utilization rate is
This implies
|𝑚 ∗ | . (15) 𝐼 Next, we prove the lower bound of the information utilization rate for the scheme; that is, the following proposition holds:
bound for the information utilization rate is: √︃ Í𝑛all 𝜆 𝑛 all 𝛿𝑖 2𝑁 𝑅 = 1 − 𝑖=1 ≥ 1 − . (21) ln 2 · 𝐼 ln 2 · 𝐼 √︃ Since 2𝜆𝑁 is extremely small for typical choices of 𝑁 (e.g., 𝑁 ≥ 20), the overall utilization rate remains relatively close to 1. According to Proposition 1, unique decoding is achieved with high probabilityl when the length of the √︃ embedded validation sufm
𝑅=
Proposition 3. To embed a payload 𝑚 ∗ , given that the maximum candidate list size is bounded by 2𝑁 and the validation suffix length is
𝑏, a lower bound on the information utilization rate is 𝑅 ≥ 1 − 𝑏|𝑚−𝑁 ∗| · ! √︃ 1−
𝑛 all
𝜆 2𝑁
ln 2·𝐼
, where 𝜆 is the security parameter, 𝑛 all is the total
number of generated tokens, and 𝐼 is the total information content of the stegotext. Proof. First, we determine the capacity lower bound on a single token. Without loss of generality, let the probability of the token be 𝑝. By Hoeffding’s inequality, we have: |𝑀2 | − 𝑝 ≥ 𝛿𝑝 ≤ exp −2𝑁 𝛿 2 𝑝 2 . Pr (16) |𝑀1 | By setting the right-hand side to be less than exp(−𝜆), rendering the probability of the event on √︃ the left-hand side negligible, we
derive an upper bound for 𝛿 as 2𝑁𝜆𝑝 2 . Therefore, after filtering based on a single token, the proportion of remaining candidate messages is at most (1 + 𝛿)𝑝. Next, consider the sequential generation of 𝑛 all tokens 𝑠 1, 𝑠 2, · · · , 𝑠𝑛all . Let the probabilities of these tokens be 𝑝 1, 𝑝 2, · · · , 𝑝𝑛all , respectively. Î𝑛all In the worst-case scenario, if 𝑖=1 (1 + 𝛿𝑖 )𝑝𝑖 ≤ 21 , an expansion step Î𝑛all is triggered. The probability of the product 𝑖=1 (1+𝛿𝑖 )𝑝𝑖 occurring Í 𝑛 all 2 2 is at most exp −2𝑁 𝑖=1 𝑝𝑖 𝛿𝑖 . By constraining this probability upper bound to be less than exp(−𝜆), we obtain a constraint on 𝛿𝑖 , Í𝑛all 2 2 namely 𝑖=1 𝑝𝑖 𝛿𝑖 ≤ 2𝜆𝑁 . Consequently, the information utilization rate implies: Í𝑛all − log2 ((1 + 𝛿𝑖 )𝑝𝑖 ) 𝑅 = 𝑖=1Í𝑛all . (17) 𝑖=1 − log2 (𝑝𝑖 ) Considering the summation in the numerator, we can separate the product terms and apply the standard inequality ln(1 + 𝑥) ≤ 𝑥: 1 ln(1 + 𝛿𝑖 ) ln 2 𝛿𝑖 ≥ − log2 (𝑝𝑖 ) − . (18) ln 2 At this point, the information utilization rate 𝑅 simplifies to: Í𝑛all 𝛿𝑖 − log2 ((1 + 𝛿𝑖 )𝑝𝑖 ) = − log2 (𝑝𝑖 ) −
𝑅 = 1 − Í𝑛all 𝑖=1 ln 2 . (19) 𝑖=1 − log2 (𝑝𝑖 ) Í𝑛all 2 2 Given that the constraint 𝑖=1 𝑝 𝛿 ≤ 𝜆𝑁 must hold for any 𝛿𝑖 , Í𝑖𝑛all𝑖 2 2 𝜆 Í𝑛all 2 and 0 ≤ 𝑝𝑖 ≤ 1, it follows that 𝑖=1 𝛿𝑖 ≤ 2𝑁 . Viewing 𝑖=1 𝛿𝑖 as
𝑖=1 𝛿𝑖
fix 𝑏 is at least 𝜆 log2 𝑒 + 𝑛𝑠𝑢 𝑓 log2 1 + 2𝜆𝑁 , where 𝑛𝑠𝑢 𝑓 is the number of tokens used to embed 𝑠𝑢 𝑓 . In our overall encoding process, the payload is embedded starting from an initial 𝑁 -bit prefix (because |𝑀0 | = 2𝑁 ) and ends after the required suffix bits are embedded. This introduces an overhead of & √︂ !' 𝜆 𝐾 = 𝜆 log2 𝑒 + 𝑛𝑠𝑢 𝑓 log2 1 + −𝑁 (22) 2𝑁 additional bits beyond the initial 𝑁 -bit prefix. Therefore, the effective utilization rate is multiplied by a coefficient 1 − |𝑚𝐾∗ | , which approaches 1 as |𝑚 ∗ | grows. □ In conclusion, under the stated conditions, the lower bound of the information utilization rate for the steganography scheme is √︃ 𝜆 𝑛 all © 𝐾 2𝑁 ª ®. 𝑅 ≥ 1 − ∗ · 1 − (23) |𝑚 | ln 2 · 𝐼 ® « ¬ Hence, the lower bound on the average embedding capacity per √ 𝜆/2𝑁 𝐾 token is 1 − |𝑚∗ | · 𝐻 − ln 2 , which is asymptotically optimal with respect to the average entropy of tokens 𝐻 .
4 Experiment & Discussion 4.1 Experiment Settings Although our steganographic scheme is not restricted to a specific carrier type, provably secure steganography has been most actively studied in text generation, as language models represent the best known technique for approximating human communication [10]. Therefore, to enable a more comprehensive and fair comparison with existing provably secure methods, our experiments primarily focus on large language model–based text generation scenarios. Baseline. We evaluated our steganography scheme against Random Sampling, representing the ideal steganography algorithm, and seven recent provably secure generative steganography algorithms, including METEOR [10] and its capacity-enhanced variant METEOR (R.), DISCOP [4] and DISCOP (R.), SparSamp [16], Shimmer [2], and the capacity-optimized group algorithm from FDPSS [11]. Each baseline was introduced in Section 2 and tested using its default parameters.
Provably Secure Steganography Based on List Decoding
Model. We evaluate our method on three purely text-generation LLMs:Mistral v0.3 [9], Qwen2 [1], and Llama3 [5], each with approximately 7 billion parameters. As models of this scale already exhibit strong instruction-following ability, all experiments are conducted in a zero-shot setting. In the main experiments, prompts are randomly sampled from the InstructWild dataset [12] and formatted with the tokenizer’s apply_chat_template function before being fed to the models. Because both our method and the provably secure baseline steganographic algorithms are distribution-agnostic and do not impose specific assumptions on the model distribution, we do not artificially constrain the decoding distribution. For each test, we ask the models to generate 1,000 samples using the full vocabulary, a base temperature of 1.0, and a maximum generation length of 800 tokens. In the main expirement, we set 𝑁 =20 and use a 20-bit validation suffix (i.e., 𝑏=20), which targets a concrete decoding-failure upper bound on the order of 10−6 . All experiments were conducted on 2 × NVIDIA A5000 GPUs (32GB RAM) and 24 × Intel Xeon w5-3423 CPUs.
4.2
Metrics
We evaluate the performance of our steganography scheme in terms of Security, Efficiency, Capacity and Correctness. 4.2.1 Security. Although our steganography scheme’s computational security has been theoretically proven in the Method Section, we further validate its security through linguistic steganalysis in adversarial scenarios and evaluate its intuitive imperceptibility based on linguistic quality. Steganalysis. We employed a classic steganalysis model TSCSW [17], which is built upon the pre-trained BERT architecture [3]to evaluate the imperceptibility of the generated stegotexts. The detectors were trained on 1,000 samples each of stegotext and corresponding cover text, randomly drawn from outputs of the same language model. The data were split in a 3:1:1 ratio for training, validation, and testing. Training was performed for three epochs with a learning rate of 1 × 10−4 . This entire procedure was repeated three times, and the final steganalysis performance was reported as the average F1 score on the test set across all runs. Linguistic Quality. The generated stegotext should meet the fundamental requirement of human perceptual concealment. We evaluate linguistic quality using perplexity (PPL) and diversity. PPL measures the fluency of generated text, with lower PPL values indicating smoother text: ! 𝐿 1 ∑︁ 𝑃𝑃𝐿 = exp − log Pr[𝑥𝑖 |x1:𝑖 −1 ] , (24) 𝐿 𝑖=1 where x represents the generated text and 𝐿 is the token count of the generated text. As for text diversity, we used the 𝑑𝑖𝑠𝑡𝑛 metric. This metric needs to find the unique pieces of tokens in the text and calculate their ratio: count(unique n-grams) 𝑑𝑖𝑠𝑡𝑛 = . (25) count(n-grams) 4.2.2 Efficiency. Time. To evaluate time efficiency, we measure the time required to generate a stego token, including both languagemodel inference and the additional computation introduced by the steganographic algorithm (e.g., sampling, and any auxiliary
XXX ’26, 978-1-4503-XXXX-X/18/06
encoding/decoding operations). We report the average runtime per generated token over the full generation process to reduce variance. Lower time indicates higher efficiency. 4.2.3 Capacity. Entropy. This represents the theoretical upper bound of the embedding capacity, measured in bits per token. The entropy is computed as: 𝐿
Entropy = −
1 ∑︁ Pr[𝑥𝑖 | 𝑥 <𝑖 ] log2 Pr[𝑥𝑖 | 𝑥 <𝑖 ], 𝐿 𝑖=1
(26)
where 𝐿 denotes the text length, and Pr[𝑥𝑖 | 𝑥 <𝑖 ] is the conditional probability of token 𝑥𝑖 given the preceding context 𝑥 <𝑖 . Embedding Capacity. This metric quantifies the average number of secret bits that can be successfully embedded and extracted, expressed as bits per token. Utilization Rate. Let 𝐵 denote the number of secret bits that can be embedded and extracted (not including the suffix) in a sentence, Í𝐿 and let 𝐼 = 𝑖=1 − log2 Pr[𝑥𝑖 | 𝑥 <𝑖 ] denote the total information (i.e., the theoretical capacity in bits) of the generated sentence of length 𝐿. The utilization rate is defined as 𝑅 = 𝐵𝐼 . Here 𝑅 ∈ [0, 1], and 𝑅 = 1 indicates optimal use of the available entropy. 4.2.4 Correctness. Success Rate We evaluate correctness using the bit-level decoding Success Rate (SR). Let x denote the original secret bitstream and x̂ the decoded bitstream, both of length|x|. 1 Í |x| We define 𝑆𝑅 = |x| 𝑗=1 𝛿 [𝑥 𝑗 , 𝑥ˆ 𝑗 ], where 𝛿 [𝑢, 𝑣] is the indicator function, which takes the value 1 if 𝑢 = 𝑣 and 0 otherwise. Consequently, 𝑆𝑅 = 1 signifies a lossless reconstruction of the secret message, whereas lower values indicate the presence of decoding errors.
4.3
Evaluation Results and Discussion
4.3.1 Capacity. As analyzed in Section 3.5, we derive lower bounds on both the information utilization rate and the embedding capacity. In the main experimental setting (𝑏 = 20, 𝑁 = 20, hence 𝐾 = 0), the lower bound on the average embedding capacity per token is √ 𝜆/2𝑁
𝐻 − ln 2 . This bound exceeds the explicit lower bounds reported by GROUP [11] (𝐻 −log2 (1+𝐻 ln 2)−0.0861), METEOR [10] ( 12 𝐻 − 12 ), DISCOP [4] (minimum entropy), and Shimmer [2] ( 23 𝐻 − 15 ) in LLMbased experiments, where the entropy H is typically small. Although some recent SOTA provably secure steganography methods, such as SparSamp [16], do not provide theoretical capacity analyses, the main experimental results in Table 1 show that our scheme achieves higher entropy utilization than SparSamp [16]. We further compare information utilization rate across large language models and secret message lengths (Fig. 3). A consistent trend is that non-instantaneous schemes (SparSamp [16] and Shimmer [2]) achieve higher capacity than instantaneous ones (METEOR [10], METEOR (R). [10], DISCOP [4], DISCOP (R.) [4], and Group [11]). This gap is structural: instantaneous constructions require the receiver to uniquely decode the embedded information from each token as soon as it is observed. In regimes where the next-token distribution is highly peaked, as is typical for LLMs, multiple payload candidates often map to the same high probability token. Consequently, instantaneous schemes must either embed a minimal
XXX ’26, 978-1-4503-XXXX-X/18/06
Model
Mistral
Qwen2
Llama3
Kaiyi Pang and Minhao Bai
Capacity
Time
Entropy bit/token
Embed ↑ bit/token
Utili.↑
Time ↓ sec./token
PPL
Dist2
Dist3
Random Sampling METEOR (R.) [10] METEOR [10] DISCOP (R.) [4] DISCOP [4] SparSamp [16] Shimmer [2] Group [11]
0.8223 0.8048 0.7794 0.7558 0.7937 0.7807 0.8163 0.9827
0.6737 0.6000 0.7439 0.4102 0.8100 0.6433 0.6519
0.6367 0.6253 0.8047 0.4002 0.8701 0.7835 0.5875
0.0552 0.0552 0.0552 0.0695 0.0606 0.0544 0.0552 0.0553
2.3359 2.2255 2.3821 2.0709 2.1052 2.3445 2.0420 2.9868
0.2447 0.2302 0.2374 0.2178 0.2458 0.2366 0.2014 0.2773
Algorithm
Linguistic Quality
Imperceptibility
Correctness
Dist4
TS-CSW F1↓
SR↑
0.4067 0.3842 0.3876 0.3541 0.3899 0.3862 0.3512 0.4387
0.5207 0.4906 0.4934 0.4532 0.4860 0.4854 0.4527 0.5482
52.39%3.87 53.97%2.99 51.11%2.37 50.08%3.02 51.10%2.79 52.67%2.35 55.34%3.94
1.000 1.000 1.000 1.000 1.000 1.000 1.000
Ours
0.8044
0.7927
0.9835
0.0529
2.1121
0.2312
0.3926
0.5013
50.06%3.91
1.000
Random Sampling METEOR (R.) [10] METEOR [10] DISCOP (R.) [4] DISCOP [4] SparSamp [16] Shimmer [2] Group [11]
1.5591 1.6269 1.6197 1.6201 1.6231 1.6238 1.6734 1.6611
0.9634 0.9551 1.2342 0.7351 1.3562 1.1528 1.0927
0.5954 0.5933 0.8458 0.4396 0.9069 0.8403 0.6197
0.0546 0.0546 0.0545 0.1296 0.1630 0.0539 0.0540 0.0545
3.5241 3.7602 3.6935 3.5792 3.7863 3.6862 3.7181 4.4333
0.3445 0.3643 0.3648 0.3576 0.3632 0.3634 0.3852 0.3991
0.5635 0.5770 0.5827 0.5753 0.5724 0.5864 0.5903 0.6151
0.7025 0.7061 0.7120 0.7104 0.6954 0.7241 0.7351 0.7431
52.69%2.39 53.81%2.90 51.84%3.19 50.29%2.83 50.77%2.68 52.71%2.20 53.59%3.25
1.000 1.000 1.000 1.000 1.000 1.000 1.000
Ours
1.5908
1.5971
0.9906
0.0517
3.8074
0.3602
0.5975
0.7237
50.59%2.07
1.000
Random Sampling METEOR (R.) [10] METEOR [10] DISCOP (R.) [4] DISCOP [4] SparSamp [16] Shimmer [2] Group [11]
0.6166 0.6724 0.6703 0.6896 0.6895 0.6653 0.7941 0.7277
0.3745 0.3640 0.5135 0.3376 0.6265 0.5733 0.4364
0.5418 0.5406 0.7656 0.4770 0.9319 0.7219 0.5807
0.0582 0.0587 0.0586 0.1093 0.1376 0.0575 0.0579 0.0584
1.8595 1.8406 1.8525 1.8371 1.9113 1.8121 2.0421 2.1106
0.1846 0.1800 0.1893 0.1816 0.1842 0.1803 0.2013 0.2122
0.3143 0.3041 0.3210 0.3073 0.3121 0.3021 0.3413 0.3490
0.4176 0.4057 0.4286 0.4109 0.4123 0.4020 0.4463 0.4545
54.10%3.15 53.27%2.72 51.94%1.81 50.43%1.93 51.92%2.46 53.30%3.08 52.51%3.20
1.000 1.000 1.000 1.000 1.000 1.000 1.000
Ours
0.6717
0.6725
0.9924
0.0523
1.8594
0.1893
0.3154
0.4240
51.21%2.07
1.000
Table 1: Main results with 𝑁 = 20 and 𝑏 = 20.
Llama3
Utilization Rate
100%
Mistral
100%
90%
90%
90%
80%
80%
80%
70%
70%
70%
60%
60%
60%
50%
50%
50%
40%
100
300
500
Secret Bits Length Method Meteor(Reordered)
40%
Meteor
100
300
Secret Bits Length Discop(Reordered) Discop
Qwen2
100%
40%
500
Group
100
Sparsamp
300
Secret Bits Length Shimmer Ours
500
Figure 3: The information utilization rate of several existing provable secure steganography schemes common prefix or forgo embedding entirely, thereby wasting portion of the available entropy. Non-instantaneous schemes relax this per-token decodability constraint and allow ambiguity to be resolved using future tokens, enabling higher entropy utilization.
Among the instantaneous baselines, DISCOP(R.) achieves the highest capacity in our experimental settings [2, 16], but it still falls short of the best non-instantaneous constructions.
Provably Secure Steganography Based on List Decoding
4.3.2 Time Efficiency. The time of our approach is predominantly limited by two factors: the time for model to generate token and the time for sampling. As shown in Table 1, even with a sampling scale of around 220 , our steganography scheme does not incur significant time overhead; its runtime is comparable to random sampling and other baseline methods. With faster sampling techniques [14, 15], the time required to generate stego tokens could be further reduced. Our scheme is even faster than DISCOP, especially its reordered variant, which must construct a Huffman tree at each time step, which leads to slightly higher runtime despite our optimized Cython implementation. 4.3.3 Linguistic Quality & Security . Similar to other provably secure steganographic constructions, Table 1 shows that the stegotext generated by our method closely matches randomly sampled text across multiple evaluation metrics, including PPL and diversity measures (Dist-2, Dist-3, and Dist-4). This is consistent with our security analysis, indicating that the stegotext is difficult to distinguish from cover text. As illustrated in Table 2, both randomly sampled text and stego text are also perceptually indistinguishable to human readers. Steganalysis results further confirm this: because
100
0.768
0.753
0.853
0.910
0.927
0.940
0.947
0.966
0.968
200
0.717
0.848
0.849
0.894
0.927
0.963
0.972
0.971
0.981
300
0.768
0.832
0.915
0.922
0.951
0.967
0.976
0.983
0.995
400
0.750
0.845
0.887
0.932
0.970
0.986
0.987
0.984
0.991
500
0.774
0.814
0.917
0.930
0.968
0.965
0.980
0.981
0.991
600
0.697
0.817
0.905
0.931
0.968
0.961
0.986
0.991
0.995
5
7
9
11
13
15
17
19
20
0.90 0.85
Utils
Secret bits length
0.95
0.80 0.75 0.70
N
100
0.639
0.702
0.838
0.881
0.930
0.918
0.948
0.930
0.956
200
0.664
0.777
0.858
0.893
0.950
0.945
0.958
0.961
0.972
300
0.634
0.738
0.855
0.892
0.946
0.949
0.973
0.976
0.976
400
0.684
0.774
0.858
0.902
0.937
0.950
0.964
0.977
0.987
500
0.667
0.791
0.858
0.894
0.939
0.967
0.983
0.980
0.989
600
0.617
0.785
0.861
0.906
0.952
0.968
0.979
0.990
0.992
5
7
9
11
13
15
17
19
20
0.95 0.90 0.85 0.80
Utils
Secret bits length
(a) Llama3
0.75 0.70 0.65
N
(b) Mistral3 100
0.662
0.737
0.812
0.856
0.941
0.892
0.915
0.957
0.957
200
0.653
0.761
0.839
0.914
0.920
0.944
0.955
0.971
0.969
0.90
300
0.664
0.793
0.811
0.899
0.945
0.933
0.967
0.975
0.972
0.85
400
0.646
0.768
0.850
0.890
0.935
0.964
0.973
0.984
0.978
0.80
500
0.664
0.793
0.734
0.915
0.945
0.960
0.972
0.984
0.984
600
0.646
0.786
0.864
0.880
0.940
0.963
0.980
0.990
0.992
5
7
9
11
13
15
17
19
20
0.95
Utils
Secret bits length
Despite their advantage, existing non-instantaneous schemes still incur avoidable capacity loss due to how they represent and update the decoding state. Shimmer [2] maintains a single intervalvalued state; when interval splitting occurs, the valid set becomes a union of disjoint intervals. Keeping all branches would lead to an exponential blowup, so Shimmer must effectively discard branches to suppress splitting, which wastes entropy and reduces utilization. SparSamp [16] improves capacity by accumulating entropy over blocks, but it does not expand a set of parallel decoding candidates when ambiguity persists; instead, it must pause active embedding (or spend additional tokens to resolve the state), again leaving part of the entropy unexploited. In contrast, our method attains the highest capacity among noninstantaneous constructions because it adopts a list-decoding view of steganographic decoding. Rather than enforcing immediate decodability or committing to a single interval/state, we maintain a bounded candidate list of message prefixes. Each generated token filters this list in proportion to its probability mass, and whenever the list becomes too small we expand it to keep the filtering process operating near the entropy rate. The remaining ambiguity is then eliminated by matching a short validation suffix. This filter–expand–match mechanism continuously harvests entropy from every token while keeping computation bounded, which explains the consistent utilization gains observed in Fig. 3 We further examine how the secret message length |𝑚 ∗ | and the candidate list size 2𝑁 affect the utilization rate (Fig. 4). Across all three large language models, for a fixed 𝑁 , longer secret messages yield higher utilization. This trend is expected because the suffix can be viewed as a fixed overhead used to enable fast and unambiguous decoding; amortizing the same suffix over more payload bits improves overall efficiency (even though suffix bits are excluded from the embedding capacity). Moreover, larger values of 𝑁 consistently yield higher utilization, which aligns with our list-decoding intuition: maintaining a larger candidate list provides more flexibility and results in higher embedding capacity.
XXX ’26, 978-1-4503-XXXX-X/18/06
0.75 0.70 0.65
N
(c) Qwen2
Figure 4: Information utilization rate of our method for different secret bit lengths and candidate list length (𝑁 ) on three LLMs (Llama3, Mistral3, and Qwen2).
provably secure schemes make steganographic sampling computationally indistinguishable from random sampling, machine-learning classifiers fail to learn effective features, yielding F1 scores close to 50%. 4.3.4 Decoding Correctness. In the Proof of Correctness section 3.3, we explain that when the suffix 𝑠𝑢 𝑓 has a length of 𝑏, the probability −𝑏 of a decoding error is at most √︃2 𝜆 𝑛 . Larger 𝑏 tightens this 1+
2𝑁
bound and can make the decoding error probability negligibly small; in our experiments we choose 𝑏 = 20 to reduce overhead while
XXX ’26, 978-1-4503-XXXX-X/18/06
still keeping the concrete upper bound extremely low. In the main experiment, where 𝑏 = 20, the upper bound for the error rate is 8.695 × 10−7 . As indicated in Table 1, no decoding errors were observed in the main experiments involving 1,000 samples.
5
Conclusion
In this paper, we revisit steganography decoding from a list-decoding perspective and categorize existing schemes into instantaneous and non-instantaneous codes. By temporarily maintaining a set of decoding candidates, non-instantaneous codes can exploit entropy more fully and achieve higher embedding capacity. Building on this insight, we propose a provably secure steganography scheme based on list decoding, which combines list expansion and suffix matching to ensure correct decoding while enabling high-capacity embedding. We provide a security and correctness proof,and derive theoretical lower bound on the embedding capacity. Extensive experiments on three popular LLMs demonstrate that our method achieves high generation quality, efficiency, and capacity.
6
Ethics Considerations
We propose a provably secure steganography scheme based on list decoding that embeds secret messages into seemingly innocuous text. We acknowledge the dual-use risk of this technology: While it protects people’s privacy to prevent censorship, it could also be exploited by malicious actors for covert coordination. We treat the secret bits as a random binary bitstream without semantic constraints in expirements so the steganography method is agnostic to content. Relative to prior provably secure text steganography [2, 4, 10, 11], our main contribution is an algorithmic design that improves capacity and decoding, rather than the introduction of the underlying ethically sensitive capability of covert communication itself. We therefore do not believe that this work materially exacerbates the ethical risks already associated with this line of research. Furthermore, we emphasize that our scheme guarantees concealment only at the content level. It does not hide network metadata or traffic patterns, which monitors can still exploit via behavioral analysis. Thus, this method should be viewed not as a standalone panacea for resisting surveillance but as a component of a broader surveillance defense strategy.
7
Open Science
Our steganography scheme is available at :https://anonymous.4open. science/r/Provably-Secure-Steganography-Based-on-List-DecodingD4E2.
8
Acknowledgement of LLM usage
We used LLMs(ChatGPT and Claude) only for limited editorial assistance, primarily to polish parts of the Introduction and to improve grammar and phrasing in the manuscript. They were not used to generate the core technical ideas, algorithms, proofs, code, experimental results, or quantitative analyses reported in this paper.
9
Track selection justification
This paper is fit for both the Software Security track and the Privacy and Anonymity track. It aligns with the Software Security track
Kaiyi Pang and Minhao Bai
because information hiding is explicitly listed within its scope, and our work on provably secure steganography falls squarely within this area. It is equally relevant to the Privacy and Anonymity track because a primary application of steganography is to resist unauthorized surveillance and enable covert communication.
Provably Secure Steganography Based on List Decoding
References [1] Jinze Bai, Shuai Bai, and Yunfei Chu et. al. 2023. Qwen Technical Report. arXiv preprint arXiv:2309.16609 (2023). [2] Minhao Bai, Kaiyi Pang, Guorui Liao, Jinshuai Yang, and Yongfeng Huang. 2025. Shimmer: a Provably Secure Steganography Based on Entropy Collecting Mechanism. In 34th USENIX Security Symposium (USENIX Security 25). 5949–5965. [3] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805 (2018). [4] 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). IEEE Computer Society, 2238–2255. [5] Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. 2024. The llama 3 herd of models. arXiv preprint arXiv:2407.21783 (2024). [6] Tina Fang, Martin Jaggi, and Katerina Argyraki. 2017. Generating Steganographic Text with LSTMs. In Proceedings of ACL 2017, Student Research Workshop. 100– 106. [7] V. Guruswami and M. Sudan. 1999. Improved decoding of Reed-Solomon and algebraic-geometry codes. IEEE Transactions on Information Theory 45, 6 (1999), 1757–1767. https://doi.org/10.1109/18.782097 [8] Nicholas J. Hopper. 2004. Toward a Theory of Steganography. Ph.D. thesis. Carnegie Mellon University, Pittsburgh, PA. [9] Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. 2023. Mistral 7B. arXiv preprint arXiv:2310.06825 (2023). [10] 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 (Virtual Event, Republic of Korea) (CCS ’21). Association for Computing Machinery, New York, NY, USA, 1529–1548. https://doi.org/10.1145/3460120. 3484550 [11] Guorui Liao, Jinshuai Yang, Weizhi Shao, and Yongfeng Huang. 2025. A framework for designing provably secure steganography. In 34th USENIX Security Symposium (USENIX Security 25). 6837–6856. [12] Jinjie Ni, Fuzhao Xue, Yuntian Deng, Jason Phang, Kabir Jain, Mahir Hitesh Shah, Zangwei Zheng, and Yang You. 2023. Instruction in the Wild: A User-based Instruction Dataset. https://github.com/XueFuzhao/InstructionWild. [13] Madhu Sudan. 1997. Decoding of Reed Solomon Codes beyond the ErrorCorrection Bound. J. Complex. 13, 1 (March 1997), 180–193. https://doi.org/10. 1006/jcom.1997.0439 [14] Alastair J Walker. 1974. New fast method for generating discrete random numbers with arbitrary frequency distributions. Electronics Letters 10, 8 (1974), 127–128. [15] Alastair J Walker. 1977. An efficient method for generating discrete random variables with general distributions. ACM Transactions on Mathematical Software (TOMS) 3, 3 (1977), 253–256. [16] 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 34th USENIX Security Symposium (USENIX Security 25). [17] Zhongliang Yang, Yongfeng Huang, and Yujin Zhang. 2020. TS-CSW: Text steganalysis and hidden capacity estimation based on convolutional sliding windows. Multimedia Tools and Applications 79 (2020), 18293–18316. [18] Zhong-Liang Yang, Xiao-Qing Guo, Zi-Ming Chen, Yong-Feng Huang, and Yu-Jin Zhang. 2018. RNN-stega: Linguistic steganography based on recurrent neural networks. IEEE Transactions on Information Forensics and Security 14, 5 (2018), 1280–1295. [19] Zhong-Liang Yang, Si-Yu Zhang, Yu-Ting Hu, Zhi-Wen Hu, and Yong-Feng Huang. 2020. VAE-Stega: linguistic steganography based on variational auto-encoder. IEEE Transactions on Information Forensics and Security 16 (2020), 880–895. [20] Zachary Ziegler, Yuntian Deng, and Alexander M 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). 1210–1215.
XXX ’26, 978-1-4503-XXXX-X/18/06
A Appendix A.1 Alias Method Since the number of samples required can be extremely large, the efficiency of standard Inverse Transform Sampling is insufficient. The complexity of traditional Inverse Transform Sampling is 𝑂 (|𝑉 |), where |𝑉 | is the size of the model’s vocabulary. If 2𝑘 samples are required, the complexity of the entire sampling flow becomes 𝑂 (2𝑘 |𝑉 |). In practice, generating 1 million samples could incur a latency of several seconds or even tens of seconds. Therefore, we introduce an efficient sampling method known as the Alias Method[14, 15], proposed by A. J. Walker in 1977. The detailed procedure is given below. The algorithm reconstructs the original distribution 𝐷 in a preparation phase into a uniform combination of sub-distributions, each Í |𝑉 | 1 containing at most two tokens, such that 𝐷 (𝑧) = 𝑖=1 |𝑉 | 𝐷𝑖 (𝑧). To construct such sub-distributions, the probability of each token is first multiplied by |𝑉 | as a weight. These weights are then redistributed into multiple normal sub-distributions that sum to 1. Specifically, tokens are divided into two categories: a low-weight list 𝑆 (weights < 1) and a high-weight list 𝐺 (weights ≥ 1). When constructing a sub-distribution, a token 𝑗 is removed from 𝑆. Since 𝑞 𝑗 < 1, a token 𝑘 is removed from 𝐺, and its weight 𝑞𝑘 is split. Part of it, 1 − 𝑞 𝑗 , is used to fill the sub-distribution (making the sum 1), while the remainder 𝑞𝑘 − (1 − 𝑞 𝑗 ) becomes the new weight for token 𝑘, which is then re-added to either 𝑆 or 𝐺. The resulting sub-distribution contains only two tokens, 𝐴𝑖 = 𝑗 and 𝐵𝑖 = 𝑘, with probabilities 𝑃 (𝐴𝑖 ) = 𝑞 𝑗 and 𝑃 (𝐵𝑖 ) = 1 − 𝑞 𝑗 . Eventually, the entire distribution 𝐷 is decomposed into a uniform combination of such sub-distributions. Once constructed, sampling is straightforward: uniformly select one of the |𝑉 | sub-distributions, then output the sample based on a comparison between a random number and 𝑃 (𝐴𝑖 ). The complexity of the preparation phase is 𝑂 (|𝑉 |), while a single sampling operation requires only one comparison, yielding 𝑂 (1) complexity. When generating 2𝑘 samples, the total complexity is 𝑂 (|𝑉 | + 2𝑘 ), which is significantly superior to repeated Inverse Transform Sampling.
A.2
Examples of generated stegotext
Table 2 shows several examples of stegotext produced by llama3 in the main experiment. It is difficult for human to perceptually distinguish between normally generated text produced by random sampling and text generated by provably secure steganographic methods.
XXX ’26, 978-1-4503-XXXX-X/18/06
Kaiyi Pang and Minhao Bai
Table 2: Examples of stegotexts generated by Llama3-8B Method
Generated Texts
Prompt
What is Steganography?
Random Sampling
Steganography is a technique of hiding secret information within a non-secret message, image, audio, or other medium. The goal is to conceal the existence of the secret information, making it difficult for unauthorized parties to detect its presence. Imagine sending a letter to a friend with a hidden message inside: you would write the secret message on the back of a seemingly ordinary letter or enclose it within an envelope with a false address......
METEOR(R.) [10]
Steganography is the practice of hiding secret information within a non-secret message, image, audio, or other medium. The goal of steganography is to conceal the existence of the secret information, making it difficult for unauthorized parties to detect its presence. In other words, steganography involves embedding a message, known as the covertext, within a seemingly innocuous medium, such as an image, video, audio file, or text......
METEOR [10]
Steganography is the practice of hiding secret information within a non-secret message, image, or file in such a way that the very existence of the secret information is not apparent. The goal of steganography is to conceal the fact that a secret message is being transmitted, rather than simply encrypting it. In other words, steganography is a technique used to communicate sensitive information securely by hiding it in plain sight......
DISCOP(R.) [4]
Steganography is a technique used to hide secret information within a non-secret message, image, audio, or video file. The goal of steganography is to conceal the existence of the secret information, making it difficult for unauthorized parties to detect its presence. In steganography, a cover text is used as a carrier to hide the secret information. The cover text can be a digital image, audio file, video, or even a text file. The secret information, known as the message, is then concealed ......
DISCOP [4]
Steganography is a method of hiding secret information within a non-secret message, image, audio, or video file. The idea is to conceal the existence of the hidden message or data, making it difficult for unauthorized parties to detect its presence. In other words, steganography is a technique that embeds a secret message or data within a cover file, such as an image, audio, or video, in a way that the presence of the hidden information is not immediately apparent...
SparSamp [16]
Steganography is the practice of hiding secret information within a non-secret message, image, audio, or video file in such a way that the very existence of the secret message is not apparent. The goal of steganography is to conceal the presence of the secret information, making it invisible to unauthorized parties. Steganography is often compared to cryptography, which is the practice of encrypting information to make it secure. While cryptography focuses on protecting the confidentiality......
Shimmer [2]
Steganography is the practice of hiding secret information within a non-secret message, image, audio file, or other medium in such a way that the very existence of the secret information is not apparent. This is in contrast to cryptography, which encrypts the secret information, making it unreadable without the proper decryption key or access. In steganography, the secret information is embedded in a way that makes it difficult to distinguish from the rest of the message, and the presence of......
Group [11]
Steganography is the practice of concealing a secret message, image, or audio file within a non-secret message, image, or audio file, called a cover object. The goal of steganography is to hide the existence of the secret message orsignal, so that only the intended recipient can detect and extract it. Steganography is often used to achieve confidentiality and authenticity of the secret information. By embedding the secret message within a seemingly innocuous object......
Ours
Steganography is the practice of hiding secret information or messages within another, seemingly innocuous, medium or format, such as an image, audio file, or text document. The purpose of steganography is to conceal the existence of the secret message, making it difficult for unauthorized parties to detect or intercept it. Steganography is different from cryptography, which focuses on encrypting and protecting the content of the message. In steganography, the message itself ......
Provably Secure Steganography Based on List Decoding
XXX ’26, 978-1-4503-XXXX-X/18/06
XXX ’26, 978-1-4503-XXXX-X/18/06
Kaiyi Pang and Minhao Bai