Fundamental Limits of Information Hiding

by Pierre Moulin and Joseph A. O'Sullivan


An information-theoretic analysis of information hiding is presented in
this talk, forming the theoretical basis for design of information-hiding 
systems.  Information hiding is an emerging research area which
encompasses applications such as copyright protection for digital media,
watermarking, fingerprinting, and steganography. 
In these applications, information is hidden within a host data set
and is to be reliably communicated to a receiver.
The host data set is purposely corrupted, but in a covert way,
designed to be imperceptible to a casual analysis. 
Next, an attacker may seek to destroy this hidden information,
and for this purpose, introduce additional distortion to the data set.
Cryptographic keys may be available to the information hider and
to the decoder.

We formalize these notions and evaluate the hiding capacity,
which upper-bounds the rates of reliable transmission and quantifies
the fundamental tradeoff between three quantities:
the achievable information-hiding rates and the allowed distortion
levels for the information hider and the attacker.  The hiding capacity
is the value of a game between the information hider and the attacker.
It is shown that existing information-hiding systems
in the literature operate far below capacity.