Efficient Provably Secure Linguistic Steganography via Range Coding
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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on10
- Language Models are Few-Shot LearnersTom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah et al.NeurIPS 2020 · 64,255 citations
- Unsupervised Cross-lingual Representation Learning at ScaleAlexis Conneau, Kartikay Khandelwal, Naman Goyal, Vishrav Chaudhary et al.ACL 2020 · 539 citations
- Provably Secure Generative Linguistic SteganographySi-yu Zhang, Zhongliang Yang, Jinshuai Yang, Yongfeng HuangACL Findings 2021 · 101 citations
- Meteor: Cryptographically Secure Steganography for Realistic DistributionsGabriel Kaptchuk, Tushar M. Jois, Matthew Green, Aviel D. RubinCCS 2021 · 50 citations
- Near-imperceptible Neural Linguistic Steganography via Self-Adjusting Arithmetic CodingJiaming Shen, Heng Ji, Jiawei HanEMNLP 2020 · 39 citations
Related papers
- A Content-Preserving Secure Linguistic SteganographyLingyun Xiang, Chengfu Ou, Xu He, Zhongliang Yang et al.AAAI 2026
- Provable Secure Steganography Based on Adaptive Dynamic SamplingKaiyi Pang, Minhao BaiUSENIX Security 2026 · 4 citations
- Perfectly Secure Steganography Using Minimum Entropy CouplingChristian Schröder de Witt, Samuel Sokota, J. Zico Kolter, Jakob Nicolaus Foerster et al.ICLR 2023 · 12 citations
- SparSamp: Efficient Provably Secure Steganography Based on Sparse SamplingYaofei Wang, Gang Pei, Kejiang Chen, Jinyang Ding et al.USENIX Security 2025
- STEAD: Robust Provably Secure Linguistic Steganography with Diffusion Language ModelYuang Qi, Na Zhao, Qiyi Yao, Benlong Wu et al.NeurIPS 2025 · 4 citations
