  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.
