A Framework for Designing Provably Secure Steganography

Steganography is a technique to transmit secret messages over a public channel so that the very existence of these secret messages can not be detected. In this field, provably secure steganography based on shared white-box samplers is a major focus due to its capability to construct secure and efficient steganographic systems on various practical channels. However, designing a novel provably secure steganography scheme remains challenging, since the scheme must maintain a nearly identical sampling distribution to any given discrete distribution while embedding secret information. Currently, there are only a few provably secure steganography schemes available, which significantly limits both practical application and theoretical research. In this paper, we propose a framework for designing provably secure steganography, with the universal security proof for schemes derived from this framework. This framework decomposes the overall complex design into three sub-processes that can be relatively easily achieved, namely Probability Recombination Module, Bin Sampling and Uniform Steganography Module. With this framework, we present several new provably secure steganography schemes and demonstrate that the recent work, Discop(base), is also encompassed by this framework. Additionally, guided by this framework, we have identified several schemes that are theoretically optimal or very effective under specified metrics and validated their effectiveness through experimental verification.