Elamur Research⌕
☰
home / papers / 2026 / Efficient Provably Secure Linguistic Steganography via Range Coding

Efficient Provably Secure Linguistic Steganography via Range Coding

Paper · 2026 · Ruiyi Yan and Yugo Murawaki

Summary

Linguistic steganography hides secret messages inside ordinary-looking generated text. Provably secure schemes keep the language model's output distribution unchanged (zero KL divergence), but they usually give up embedding capacity or speed. The authors, Yan and Murawaki of Kyoto University, return to range coding, a classical entropy-coding technique. Unlike earlier methods, which handle the message as discrete bits, it treats the whole message as a single decimal value. Their first, vanilla version has two security flaws: it slightly distorts the token distribution, and it reuses randomness. They fix both with rotation range-coding (RRC), which adds a rotation step. RRC needs no training and works with any model. The authors prove zero KL divergence and computational security, and they argue that RRC uses close to all of the available entropy. Tests on GPT-2, OPT-1.3b and Llama-2-7b show that RRC turns nearly all token entropy into hidden bits while remaining fast. It beats prior provably secure baselines such as Discop and SparSamp. This makes high-throughput covert communication practical without sacrificing detectability guarantees.

Key points

  • On GPT-2, RRC embeds 5.93 bits/token from 5.93 bits/token of entropy (99.98% utilization) at 1554.66 bits/s with zero KL divergence. The best zero-KL baseline reached about 96.8% utilization at roughly 1268 bits/s.
  • Utilization stays near 100% across message lengths. For messages of 64–1024 bits, speed holds at about 1500 bits/s. Messages of 8192 bits and beyond are supported via Python's decimal module.
  • Fine-tuned BERT and RoBERTa steganalysis discriminators detect RRC texts at roughly chance level (about 50% accuracy).
  • In a human evaluation, three judges rated 250 stegotexts and 250 cover texts per model. Their accuracy was 46.6–50.6%, which is again chance level.
  • Sender and receiver must agree on the message length in advance. The near-100% utilization is shown empirically, not proven rigorously. Code: github.com/ryehr/RRC_steganography.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Kyoto UniversityKyoto · Japan42 works · 8,235 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksComputer Vision and Pattern Recognition · 3,486 worksEngineering · 188 worksElectrical and Electronic Engineering · 33 works

Cite

Cite as Ruiyi Yan and Yugo Murawaki. 2026. Efficient Provably Secure Linguistic Steganography via Range Coding. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.acl-long.39

@inproceedings{yan2026efficient,
  title = {{Efficient Provably Secure Linguistic Steganography via Range Coding}},
  author = {Ruiyi Yan and Yugo Murawaki},
  booktitle = {Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2026},
  doi = {10.18653/v1/2026.acl-long.39},
  url = {https://doi.org/10.18653/v1/2026.acl-long.39}
}

References

41 references, 6 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. 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.
  2. Anthropic. 2024. The claude 3 model family: Opus, sonnet, haiku. https://www-cdn.anthropic.com/ de8ba9b01c9ab7cbabf5c33b80b7bbc618857627/ Model_Card_Claude_3.pdf. ↗
  3. 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. Non-determinism of "deterministic" llm settings. Preprint, arXiv:2408.04667. — [arXiv:2408.04667](https://arxiv.org/abs/2408.04667) find
  4. 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… find
  5. Christian Cachin. 1998. An information-theoretic model for steganography. In Information Hiding, pages 306–318, Berlin, Heidelberg. Springer Berlin Heidelberg. find
  6. 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.
  7. Falcon Dai and Zheng Cai. 2019. Towards near-imperceptible steganographic text. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 4303–4308, Florence, Italy. Association for Computational Linguistics. find
  8. 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. find
  9. 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,…
  10. 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. find
  11. A.A. Fedotov, P. Harremoes, and F. Topsoe. 2003. Refinements of pinsker’s inequality. IEEE Transactions on Information Theory, 49(6):1491–1498. find
  12. 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. find
  13. Nicholas Hopper, Luis von Ahn, and John Langford. 2009. Provably secure steganography. IEEE Transactions on Computers, 58(5):662–676. find
  14. 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. find
  15. 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… find
  16. 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. find
  17. Diederik P. Kingma and Jimmy Ba. 2017. Adam: A method for stochastic optimization. Preprint, arXiv:1412.6980.
  18. Tri Van Le. 2003. Efficient provably secure public key steganography. Cryptology ePrint Archive, Paper 2003/156. find
  19. 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. find
  20. 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 (Vo… find
  21. 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. find
  22. 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. find
  23. 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. find
  24. J. Rissanen and G. G. Langdon. 1979. Arithmetic coding. IBM Journal of Research and Development, 23(2):149–162. find
  25. Jiaming Shen, Heng Ji, and Jiawei Han. 2020. Near-imperceptible 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. find
  26. Gustavus J. Simmons. 1984. The Prisoners’ Problem and the Subliminal Channel, pages 51–67. Springer US, Boston, MA. find
  27. 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.
  28. 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. find
  29. 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. find
  30. Lingyun Xiang, Shuanghui Yang, Yuhang Liu, Qian Li, and Chengzhang Zhu. 2020. Novel linguistic steganography based on character-level text generation. Mathematics, 8(9). find
  31. Ruiyi Yan, Chenhui Chu, Zhongliang Yang, and Yugo Murawaki. 2025. A comprehensive survey on linguistic steganography: Methods, countermeasures, evaluation, and challenges. find
  32. 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 Linguist… find
  33. Ruiyi Yan, Tian Song, and Yating Yang. 2024a. A near-imperceptible disambiguating approach via verification for generative linguistic steganography. In 2024 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pages 1638–1643. find
  34. Ruiyi Yan, Tian Song, and Yating Yang. 2024b. To-kenfree: A tokenization-free generative linguistic steganographic approach with enhanced imperceptibility. In 2024 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pages 449– 455. find
  35. Ruiyi Yan, Yating Yang, and Tian Song. 2023. A secure and disambiguating approach for generative linguistic steganography. IEEE Signal Processing Letters, 30:1047–1051. find
  36. 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. find
  37. Zhong-Liang Yang, Xiao-Qing Guo, Zi-Ming Chen, Yong-Feng Huang, and Yu-Jin Zhang. 2019b. Rnn-stega: Linguistic steganography based on recurrent neural networks. IEEE Transactions on Information Forensics and Security, 14(5):1280–1295. find
  38. Zhong-Liang Yang, Si-Yu Zhang, Yu-Ting Hu, Zhi-Wen Hu, and Yong-Feng Huang. 2021. Vae-stega: Linguistic steganography based on variational autoencoder. IEEE Transactions on Information Forensics and Security, 16:880–895. find
  39. 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. find
  40. 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-trai…
  41. 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, Ch… find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/yan-2026-efficient-provably-secure-linguistic-steganography/