Bonn-Aachen International Center
for Information Technology





city life
cosec >students >Teaching >Winter 2007/2008 

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.

Imprint, webmaster & more