On the universal steganography of optimal rate

In this work, we present the first secure stegosystem in the common computational model which, for any communication channel, is provably secure, reliable, and has nearly optimal bandwidth, but needs super-polynomial time. This solves several open problems about secret-key steganography in the computational model. In particular, our result answers affirmatively the question whether there exists a secure and reliable universal system of rate asymptotically larger than log⁡κ, where κ is the security parameter. Next, we prove a lower bound on the query complexity of stegosystems showing that our construction is optimal. This lower bound extends the results by Hopper et al. (2009) [19] and by Dedić et al. (2009) [22]. We also discuss universal steganography of optimal rate in the information-theoretic setting. We prove that an exponential number of samples is needed to embed messages in documents of high min-entropy. Our results, together with the result by Cachin (2004) [16], show that the situation of universal steganography in the computational and in the information-theoretic model is analogous: optimal universal steganography exists, but the protocols need super-polynomial time.