# Perfectly Secure Steganography Using Minimum Entropy Coupling

arXiv: https://arxiv.org/abs/2210.14889 · HTML: https://mlsanity.com/paper/2210.14889/

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 29 references that are in the map.
- First posted on arXiv 24 Oct 2022.

## Builds on (most cited first, 12 of 12)

- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Natural TTS Synthesis by Conditioning WaveNet on Mel Spectrogram Predictions](https://mlsanity.com/paper/1712.05884/) (2017)
- [Image Transformer](https://mlsanity.com/paper/1802.05751/) (2018)
- [Efficient Neural Audio Synthesis](https://mlsanity.com/paper/1802.08435/) (2018)
- [TorchAudio: Building Blocks for Audio and Speech Processing](https://mlsanity.com/paper/2110.15018/) (2021)
- [Neural Linguistic Steganography](https://mlsanity.com/paper/1909.01496/) (2019)
- [Provably Secure Generative Linguistic Steganography](https://mlsanity.com/paper/2106.02011/) (2021)
- [Towards Near-imperceptible Steganographic Text](https://mlsanity.com/paper/1907.06679/) (2019)
- [Entropic Causal Inference](https://mlsanity.com/paper/1611.04035/) (2016)
- [Communicating via Markov Decision Processes](https://mlsanity.com/paper/2107.08295/) (2021)
- [Minimum--Entropy Couplings and their Applications](https://mlsanity.com/paper/1901.07530/) (2019)

## Built on by (most cited first, 30 of 44)

- [Secret Collusion among AI Agents: Multi-Agent Deception via Steganography](https://mlsanity.com/paper/2402.07510/) (2024)
- [Open Challenges in Multi-Agent Security: Towards Secure Systems of Interacting AI Agents](https://mlsanity.com/paper/2505.02077/) (2025)
- [Advancing Beyond Identification: Multi-bit Watermark for Large Language Models](https://mlsanity.com/paper/2308.00221/) (2023)
- [Hidden in Plain Text: Emergence & Mitigation of Steganographic Collusion in LLMs](https://mlsanity.com/paper/2410.03768/) (2024)
- [Pseudorandom Error-Correcting Codes](https://mlsanity.com/paper/2402.09370/) (2024)
- [Prompting a Pretrained Transformer Can Be a Universal Approximator](https://mlsanity.com/paper/2402.14753/) (2024)
- [Excuse me, sir? Your language model is leaking (information)](https://mlsanity.com/paper/2401.10360/) (2024)
- [Watermarking Language Models with Error Correcting Codes](https://mlsanity.com/paper/2406.10281/) (2024)
- [The Steganographic Potentials of Language Models](https://mlsanity.com/paper/2505.03439/) (2025)
- [TrojanStego: Your Language Model Can Secretly Be A Steganographic Privacy Leaking Agent](https://mlsanity.com/paper/2505.20118/) (2025)
- [All Code, No Thought: Current Language Models Struggle to Reason in Ciphered Language](https://mlsanity.com/paper/2510.09714/) (2025)
- [A Decision-Theoretic Formalisation of Steganography With Applications to LLM Monitoring](https://mlsanity.com/paper/2602.23163/) (2026)
- [Towards Measuring Goal-Directedness in AI Systems](https://mlsanity.com/paper/2410.04683/) (2024)
- [Detecting Multi-Agent Collusion Through Multi-Agent Interpretability](https://mlsanity.com/paper/2604.01151/) (2026)
- [Exploring the Relevance of Data Privacy-Enhancing Technologies for AI Governance Use Cases](https://mlsanity.com/paper/2303.08956/) (2023)
- [Provably Secure Disambiguating Neural Linguistic Steganography](https://mlsanity.com/paper/2403.17524/) (2024)
- [OD-Stega: LLM-Based Relatively Secure Steganography via Optimized Distributions](https://mlsanity.com/paper/2410.04328/) (2024)
- [Minimum Entropy Coupling with Bottleneck](https://mlsanity.com/paper/2410.21666/) (2024)
- [Scheming Ability in LLM-to-LLM Strategic Interactions](https://mlsanity.com/paper/2510.12826/) (2025)
- [Tool Use Enables Undetectable Steganography in Multi-Agent LLM Systems](https://mlsanity.com/paper/2606.28425/) (2026)
- [Unelicitable Backdoors in Language Models via Cryptographic Transformer Circuits](https://mlsanity.com/paper/2406.02619/) (2024)
- [Voluntary Collusion with Secret Tools in Competing LLM Agents](https://mlsanity.com/paper/2605.27593/) (2026)
- [Injecting Undetectable Backdoors in Obfuscated Neural Networks and Language Models](https://mlsanity.com/paper/2406.05660/) (2024)
- [PSyDUCK: Training-Free Steganography for Latent Diffusion](https://mlsanity.com/paper/2501.19172/) (2025)
- [Efficient Provably Secure Linguistic Steganography via Range Coding](https://mlsanity.com/paper/2604.08052/) (2026)
- [Learning to Match Unpaired Data with Minimum Entropy Coupling](https://mlsanity.com/paper/2503.08501/) (2025)
- [Provable Secure Steganography Based on Adaptive Dynamic Sampling](https://mlsanity.com/paper/2504.12579/) (2025)
- [Consensus Sampling for Safer Generative AI](https://mlsanity.com/paper/2511.09493/) (2025)
- [Anchored Sliding Window: Toward Robust and Imperceptible Linguistic Steganography](https://mlsanity.com/paper/2604.09066/) (2026)
- [An Application-Layer Multi-Modal Covert-Channel Reference Monitor for LLM Agent Egress](https://mlsanity.com/paper/2605.20734/) (2026)

## Abstract (arXiv)

Steganography is the practice of encoding secret information into innocuous content in such a manner that an adversarial third party would not realize that there is hidden meaning. While this problem has classically been studied in security literature, recent advances in generative models have led to a shared interest among security and machine learning researchers in developing scalable steganography techniques. In this work, we show that a steganography procedure is perfectly secure under Cachin (1998)'s information-theoretic model of steganography if and only if it is induced by a coupling. Furthermore, we show that, among perfectly secure procedures, a procedure maximizes information throughput if and only if it is induced by a minimum entropy coupling. These insights yield what are, to the best of our knowledge, the first steganography algorithms to achieve perfect security guarantees for arbitrary covertext distributions. To provide empirical validation, we compare a minimum entropy coupling-based approach to three modern baselines -- arithmetic coding, Meteor, and adaptive dynamic grouping -- using GPT-2, WaveRNN, and Image Transformer as communication channels. We find that the minimum entropy coupling-based approach achieves superior encoding efficiency, despite its stronger security constraints. In aggregate, these results suggest that it may be natural to view information-theoretic steganography through the lens of minimum entropy coupling.