Key-Efficient Steganography with Provable Security Guarantees
Aggelos Kiayias (University of Connecticut), Alexander Russell (University of Connecticut) and Narasimha Shashidhar (Sam Houston State University)
Steganographic protocols enable one to embed covert messages into inconspicuous data over a public communication channel in such a way that no one, aside from the sender and the intended receiver, can even detect the presence of the secret message. In this paper, we provide a new provably-secure, private-key steganographic encryption protocol secure in the framework of Hopper et al. We first present a "one-time stegosystem" that allows two parties to transmit messages of length at most that of the shared key with information-theoretic security guarantees; employing a pseudorandom generator (PRG) then permits secure transmission of longer messages in a striaghtforward manner. The advantage of our construction in comparison with previous work is key-length efficiency: in the information-theoretic setting our protocol embeds a n bit message using a shared secret key of length (1 + o(1))n while achieving security 2^{−n/log^{O(1)}n}: this gives a rate of key length over message length that converges to 1 as n→∞; the previous best result achieved a constant rate > 1 regardless of the security offered. In this sense, our protocol is the first truly key-length efficient steganographic system. Furthermore, in our protocol, we can permit a portion of the shared secret key to be public while retaining precisely n private key bits. In this setting, by separating the public and the private randomness of the shared key, we achieve security of 2^{−n}. Our result comes as an effect of a novel application of randomness extractors to stegosystem design.
[Paper] [Presentation]