SparSamp: Efficient Provably Secure Steganography Based on Sparse Sampling

Abstract

Steganography embeds confidential data within seemingly harmless communications. Provable security in steganography, a long-sought goal, has become feasible with deep generative models. However, current methods often either compromise security or introduce significant computational complexity, failing to provide secure and efficient covert communication. This paper introduces SparSamp, an efficient provably secure steganography method based on sparse sampling. SparSamp embeds messages by converting them into message-driven sampling. It enhances extraction accuracy and embedding capacity by increasing the sampling intervals and making the sampling process sparse. SparSamp preserves the original probability distribution of the generative model, thus ensuring security. It introduces only $O(1)$ additional complexity per sampling step, which does not impact the speed of model generation, resulting in the fastest embedding speed available. SparSamp is designed to be plug-and-play; message embedding can be achieved by simply replacing the sampling component of an existing generative model with SparSamp. We implemented SparSamp in text, image, and audio generation models. It can achieve embedding speeds of up to 755 bits/second with GPT-2, 5046 bits/second with DDPM, and 9,223 bits/second with WaveRNN, enabling secure covert communication.