Efficient Provably Secure Linguistic Steganography via Range Coding

Ruiyi Yan; Yugo Murawaki

cs.CLApr 9, 2026

Efficient Provably Secure Linguistic Steganography via Range Coding

Authors: Ruiyi Yan, Yugo Murawaki

Organizations: Graduate School of Informatics, Kyoto University

Abstract

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.

Figures & tables

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.

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.

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.

Method	Avg / Max KLD (bits/token) $\downarrow$	Capacity (bits/token) $\uparrow$	Entropy (bits/token)	Utilization (%) $\uparrow$	Speed (bits/s) $\uparrow$
Multinomial sampling	0 / 0	N/A	5.86	N/A	N/A
AC	1.95E-03 / 3.01E-02	5.86	5.87	99.83	1025.36
ADG	1.60E-04 / 1.57E-03	4.81	5.89	81.60	36.45
Meteor w/o sort	4.22E-02 / 1.16E-01	4.17	5.79	71.96	950.27
Meteor w/ sort	4.11E-02 / 1.16E-01	4.77	5.81	82.08	25.25
iMEC	0 / 0	4.16	5.83	71.44	27.30

Table 1: Quantitative comparison with previous steganographic methods on GPT-2.

Message length (bits)	32	64	128	256	512	1024	2048	4096	8192
Utilization (%) $\uparrow$	99.86	99.19	99.98	99.89	99.77	99.93	100.35	100.43	99.99
Speed (bits/s) $\uparrow$	1390.23	1496.88	1554.66	1572.40	1475.68	1511.83	1191.88	880.82	604.76
Running time (s)	0.023	0.043	0.082	0.163	0.374	0.677	1.718	4.650	13.546

Table 2: Average results on utilization, speed and running time of RRC steganography across various message lengths

l

on GPT-2.

Model	Accuracy	Precision	Recall	F1
GPT-2	47.8%	47.8%	47.2%	47.5%
OPT-1.3B	46.6%	46.2%	41.2%	43.6%
Llama-2-7B	50.6%	50.6%	52.4%	51.5%

Table 3: Human evaluation results across different models.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Method	Avg / Max KLD (bits/token) $\downarrow$	Capacity (bits/token) $\uparrow$	Entropy (bits/token)	Utilization (%) $\uparrow$	Speed (bits/s) $\uparrow$
Multinomial sampling	0 / 0	N/A	4.59	N/A	N/A
AC	1.85E-03 / 1.13E-02	4.64	4.65	99.81	352.09
ADG	1.38E-04 / 1.61E-03	3.45	4.64	74.20	25.29
Meteor w/o sort	2.80E-02 / 8.34E-02	3.13	4.54	69.03	410.79
Meteor w/ sort	2.77E-02 / 8.12E-02	3.65	4.52	80.76	46.02
iMEC	0 / 0	3.24	4.61	70.24	19.78

Appendix

Table 4: Quantitative comparison with previous steganographic methods on OPT-1.3b.

Method	Avg / Max KLD (bits/token) $\downarrow$	Capacity (bits/token) $\uparrow$	Entropy (bits/token)	Utilization (%) $\uparrow$	Speed (bits/s) $\uparrow$
Multinomial sampling	0 / 0	N/A	3.46	N/A	N/A
AC	6.92E-04 / 9.90E-03	3.53	3.52	100.33	104.37
ADG	1.81E-04 / 3.90E-03	2.41	3.54	68.14	21.15
Meteor w/o sort	1.24E-02 / 4.00E-02	2.42	3.50	69.14	98.71
Meteor w/ sort	1.21E-02 / 4.19E-02	2.89	3.53	81.84	50.26
iMEC	0 / 0	2.48	3.43	72.35	10.30

Appendix

Table 5: Quantitative comparison with previous steganographic methods on Llama-2-7b.

Message length (bits)	32	64	128	256	512	1024	2048	4096	8192
Utilization (%) $\uparrow$	100.09	99.26	100.67	100.35	100.30	100.02	100.14	100.14	100.08
Speed (bits/s) $\uparrow$	685.32	745.03	750.41	720.93	701.11	588.33	403.20	248.71	184.42
Running time (s)	0.047	0.086	0.171	0.355	0.730	1.740	5.079	16.469	44.421

Appendix

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)	32	64	128	256	512	1024	2048	4096	8192
Utilization (%) $\uparrow$	102.01	100.29	101.41	100.52	100.25	100.31	100.35	100.17	100.04
Speed (bits/s) $\uparrow$	142.67	144.63	146.24	142.00	126.51	92.65	79.38	63.21	46.10
Running time (s)	0.224	0.443	1.143	1.803	4.047	11.052	25.800	64.800	177.701

Appendix

Table 7: Average results on utilization, speed and running time of RRC steganography across various message lengths

l

on Llama-2-7b.

Steganalysis model	GPT-2		OPT-1.3b		Llama-2-7b
Steganalysis model	RRC (ours)	SparSamp	RRC (ours)	SparSamp	RRC (ours)	SparSamp
bert-base-uncased	49.3%	49.9%	48.1%	48.6%	49.7%	50.9%
roberta-base	51.1%	50.5%	50.1%	49.7%	51.3%	50.5%
roberta-large	48.9%	49.2%	52.6%	51.8%	47.7%	47.6%

Appendix

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	GPT-2	OPT-1.3b	Llama-2-7b
Multinomial sampling	81.05	74.09	74.99
SparSamp	83.56	73.18	73.37
RRC steganography (Ours)	82.79	72.66	75.24

Appendix

Table 9: Comparison of median perplexity between RRC steganography and SparSamp steganography under cases where models for steganography vary.

Method	Avg / Max KLD (bits/token) $\downarrow$	Capacity (bits/token) $\uparrow$	Entropy (bits/token)	Utilization (%) $\uparrow$	Speed (bits/s) $\uparrow$
Implemented in GPT-2
Vanilla RC steganography	1.67E-14 / 5.73E-12	5.94	5.93	100.20	1605.31
RRC steganography	0 / 0	5.93	5.93	99.98	1554.66
Implemented in OPT-1.3b
Vanilla RC steganography	1.46E-14 / 4.13E-12	4.70	4.69	100.19	770.49
RRC steganography	0 / 0	4.70	4.67	100.67	750.41

Appendix

Table 10: Comparison between vanilla RC steganography and RRC steganography in various metrics.

Language Model Steganography

See all 23 papers

Anchored Sliding Window: Toward Robust and Imperceptible Linguistic Steganography
Apr 10, 2026Ruiyi Yan, Shiao Meng, Yugo MurawakiLanguage Model Steganography Language Model Robustness
Graduate School of Informatics, Kyoto University · School of Software, Tsinghua University
A Comprehensive Survey on Linguistic Steganography: Methods, Countermeasures, Evaluation, and Challenges
Aug 29, 2026Ruiyi Yan, Chenhui Chu, Zhongliang Yang +1Language Model Steganography
Graduate School of Informatics, Kyoto University · School of Cyberspace Security, Beijing University of Posts and Telecommunications
Text Steganography with Dynamic Codebook and Multimodal Large Language Model
Apr 22, 2026Jianxin Gao, Ruohan Lei, Wanli PengLLM Security Language Model Steganography
China Agricultural University Beijing, China

Apr 10, 2026J/K move · Enter open · S save

Anchored Sliding Window: Toward Robust and Imperceptible Linguistic Steganography

Ruiyi Yan, Shiao Meng, Yugo Murawaki

Graduate School of Informatics, Kyoto University · School of Software, Tsinghua University

Language Model Steganography Language Model Robustness

Open paper AskPDF arXiv

Linguistic steganography based on language models typically assumes that steganographic texts are transmitted without alteration, making them fragile to even minor modifications. While previous work mitigates this fragility by limiting the context window, it significantly compromises text quality. In this paper, we propose the anchored sliding window (ASW) framework to improve imperceptibility and robustness. In addition to the latest tokens, the prompt and a bridge context are anchored within the context window, encouraging the model to compensate for the excluded tokens. We formulate the optimization of the bridge context as a variant of prompt distillation, which we further extend using self-distillation strategies. Experiments show that our ASW significantly and consistently outperforms the baseline method in text quality, imperceptibility, and robustness across diverse settings. The code is available at github.com/ryehr/ASW_steganography.

Abstract

Language Model Steganography

Explore similar work

Anchored Sliding Window: Toward Robust and Imperceptible Linguistic Steganography

A Comprehensive Survey on Linguistic Steganography: Methods, Countermeasures, Evaluation, and Challenges

Text Steganography with Dynamic Codebook and Multimodal Large Language Model