Provably Secure Steganography

How to hide messages imperceptibly?

Must-read papers:

Category	Paper	Abbr.	Message Embedding Domain	Drawbacks
Basic Theories	Communication Theory of Secrecy Systems Shannon. BSTJ ’49	-	-	-
	An Information-Theoretic Model for Steganography Cachin. IH ’98	-	-	-
	Chapter 6: Steganographic Security, in Steganography in Digital Media: Principles, Algorithms, and Applications Fridrich. 2009	-	-	-
Rejection sampling-based	Provably Secure Steganography Hopper et al. CRYPTO ’02	RejSamp	f(stego)	Slow & Inefficient
	Public-Key Steganography von Ahn and Hopper. EUROCRYPT ’04
	Public-Key Steganography with Active Attacks Backes and Cachin. TCC ’05
Arithmetic coding-based	Efficient Provably Secure Public Key Steganography Le. IACR ePrint ’03	AC	Token indexes	Not secure
	Provably Secure Generative Steganography Based on Autoregressive Model Yang et al. IWDW ’18
	Neural Linguistic Steganography Ziegler et al. EMNLP ’19
	Distribution-Preserving Steganography Based on Text-to-Speech Generative Models Chen et al. TDSC ’21
	Meteor: Cryptographically Secure Steganography for Realistic Distributions Kaptchuk et al. CCS ’21	Meteor	Token indexes	Slow (w/ sort) or Inefficient (w/o sort)
Grouping-based	Provably Secure Generative Linguistic Steganography Zhang et al. Findings of ACL ’21	ADG	Group indexes	Not secure
Coupling-based	Perfectly Secure Steganography Using Minimum Entropy Coupling Witt et al. ICLR ’23	iMEC	Token indexes	Slow
Distribution copies-based	Discop: Provably Secure Steganography in Practice Based on “Distribution Copies” Ding et al. S&P ’23	Discop	Distribution copy indexes	Symmetric-key only
Review	Provably Secure Steganography: Theory, Application and Prospects (in Chinese) Zhang et al. J.Cybersecurity (CN) ’23	-	-	-

Optional reference papers (generative linguistic steganography):

• Generating Steganographic Text with LSTMs
• RNN-Stega: Linguistic Steganography Based on Recurrent Neural Networks
• Towards Near-imperceptible Steganographic Text
• Near-imperceptible Neural Linguistic Steganography via Self-Adjusting Arithmetic Coding

Keywords: information hiding, steganography, provably secure steganography, rejection sampling, arithmetic coding, adaptive dynamic grouping, distribution copies, minimum entropy coupling

关键词：信息隐藏，隐写，可证明安全隐写，拒绝采样，算术编码，动态自适应分组，分布副本，最小熵耦合