Information-Theoretic Analysis of Information Hiding

[Don Davis]

"An electrical engineer at Washington University
 in St. Louis has devised a theory that sets the
 limits for the amount of data that can be hidden
 in a system and then provides guidelines for how
 to store data and decode it. Contrarily, the
 theory also provides guidelines for how an
 adversary would disrupt the hidden information.

"The theory is a fundamental and broad-reaching
 advance in information and communication systems
 that eventually will be implemented in commerce
 and numerous homeland security applications --
 from detecting forgery to intercepting and
 interpreting messages sent between terrorists.

"Using elements of game, communication and
 optimization theories, Jody O'Sullivan, Ph.D.,
 professor of electrical engineering at Washington
 University in St. Louis, and his former graduate
 student, Pierre Moulin, Ph.D., now at the
 University of Illinois, have determined the
 fundamental limits on the amount of information
 that can be reliably hidden in a broad class of
 data or information-hiding problems, whether they
 are in visual, audio or print media."

http://www.eurekalert.org/pub_releases/2003-07/wuis-tch071303.php


---------------


Information--Theoretic Analysis of Information Hiding

by Pierre Moulin and Joseph A. O'Sullivan

Abstract:

"An information--theoretic analysis of information
 hiding is presented in this paper, 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, finger-
 printing, steganography, and data embedding.  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 intentionally 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.  Side information
 (in the form of cryptographic keys and/or information
 about the host signal) may be available to the information
 hider and to the decoder.

"We formalize these notions and evaluate the {\em 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.  The optimal attack strategy is the
 solution of a particular rate-distortion problem, and
 the optimal hiding strategy is the solution to a channel
 coding problem.  The hiding capacity is derived by
 extending the Gel'fand-Pinsker theory of communication
 with side information at the encoder.  The extensions
 include the presence of distortion constraints, side
 information at the decoder, and unknown communication
 channel.  Explicit formulas for capacity are given in
 several cases, including Bernoulli and Gaussian problems,
 as well as the important special case of small distortions.
 In some cases, including the last two above, the hiding
 capacity is the same whether or not the decoder knows
 the host data set.  It is shown that many existing
 information--hiding systems in the literature operate
 far below capacity." 

Sept. '02 version of the paper:

http://www.ifp.uiuc.edu/~moulin/Papers/IThiding99r.ps.gz

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com