Efficient Steganography with Provable Security Guarantees
Yona Raekow (Fraunhofer SCAI, Bonn)
Thursday, 15 November, 2007, 1500 sharp (s.t), b-it 1.25 (cosec meeting room)
In steganography, Alice an Bob wish to communicate securely in the presence of an adversary called the "Warden" that monitors whether they exchange "conspicious" messages. There have been two approaches in Steganography to solve this so called "prisoner's problem", one based on information theory and one based on complexity theory.
In this talk we focus on the complexity theoretic approach and present a stegosystem that is secure under complexity theoretic asssumptions. Most steganographic constructions that come with provable security guarantees are instantiations of the the so called "rejection-sampling" procedure, that will be introduced in the talk.
Based on the rejection sampling procedure and a combinatorial construction - a function family that is almost t-wise independent - a so called one-time stegosystem is developed, which is analogue to the one-time pad in cryptography.
Given such a one-time stegosystem it is fairly straightforward to construct provably secure steganographic encryption for longer messages by using a pseudorandom number generator to stretch a random seed that is shared between the sender and the receiver to sufficient length. The resulting stegosystem is provably secure under the assumption that one-way functions exist.