[13845] in cryptography@c2.net mail archive
Information-Theoretic Analysis of Information Hiding
daemon@ATHENA.MIT.EDU (Don Davis)
Tue Jul 15 08:48:02 2003
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Tue, 15 Jul 2003 00:30:49 -0400
To: cryptography@metzdowd.com
From: Don Davis <don@mit.edu>
"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@metzdowd.com
