An information-theoretic model for steganography.
An information-theoretic model for steganography with a passive adversary is proposed. The adversary's task of distinguishing between an innocent cover message C and a modified message S containing hidden information is interpreted as a hypothesis testing problem. The security of a steganographic system is quantified in terms of the relative entropy (or discrimination) between the distributions of C and S, which yields bounds on the detection capability of any adversary. It is shown that secure steganographic schemes exist in this model provided the covertext distribution satisfies certain conditions. A universal stegosystem is presented in this model that needs no knowledge of the covertext distribution, except that it is generated from independently repeated experiments.
Introduction
Steganography is the art and science of hiding information such that its presence cannot be detected.
Motivated by growing concern about the protection of intellectual property on the Internet and by
the threat of a ban for encryption technology, the interest in techniques for information hiding has
been increasing over the recent years [And96]. Two general directions can be distinguished within
information hiding scenarios: protection only against the detection of a message by a passive
adversary and hiding a message such that not even an active adversary can remove it. A survey of
current steganography can be found in [AP98].
Steganography with a passive adversary is perhaps best illustrated by Simmons' ``Prisoners'
Problem" [Sim84]. Alice and Bob are in jail and wish to devise an escape plan. All their communication
is observed by the adversary (the warden), who will thwart their plan by transferring
them to a high-security prison as soon as he detects any sign of a hidden message. Alice and Bob
succeed if Alice can send information to Bob such that Eve does not become suspicious.
Hiding information from active adversaries is a different problem since the existence of a hidden
message is publicly known, such as in copyright protection schemes. Steganography with active
adversaries can be divided into watermarking and fingerprinting. Watermarking supplies digital
objects with an identification of origin; all objects are marked in the same way. Fingerprinting,
conversely, attempts to identify individual copies of an object by means of embedding a unique
marker in every copy that is distributed. If later an illegal copy is found, the copyright owner can
identify the buyer by decoding the hidden information ("traitor tracing") [NFC94, PS96, PW97].

Research supported by the Swiss National Science Foundation (SNF).
Since most objects to be protected by watermarking or fingerprinting consist of audio or image
data, these data types have received most attention so far. A number of generic hiding techniques
have been developed whose effects are barely perceptible for humans but can withstand tampering
by data transformations that essentially conserve its contents [CKLS96, BGML96].
A common model and terminology for information hiding has been established at the 1996
Information Hiding Workshop [Pfi96]. An original, unaltered message is called covertext; the sender
Alice tries to hide an embedded message by transforming the covertext using a secret key. The
resulting message is called the stegotext and is sent to the receiver Bob. Similar to cryptography, it
is assumed that the adversary Eve has complete information about the system except for a secret
shared by Alice and Bob that guarantees the security. However, the model does not include a
formal notion of security.
In this paper, we introduce an information-theoretic model for steganography with a passive
adversary. We propose a security notion that is based on hypothesis testing : Upon observing a
message sent by Alice, the adversary has to decide whether it is an original covertext C or contains
an embedded message and is a stegotext S. This is the problem of distinguishing two different
explanations for the observed data that is investigated in statistics and in information theory as
"hypothesis testing." We follow the information-theoretic (non-Bayesian) approach as presented by
Blahut [Bla87] using the relative entropy function as the basic measure of the information contained
in an observation. Thus, we use the relative entropy D(PC kP S ) between PC and P S to quantify
the security of a steganographic system (or stegosystem for short) against passive attacks. If the
covertext and stegotext distributions are equal and D(PC kP S the stegosystem is perfectly
secure and the adversary can have no advantage over merely guessing without even observing a
message.
However, some caution has to be exerted using this model: On the one hand, information-theoretic
methods have been applied with great success to the problems of information encoding
and transmission, starting with Shannon's pioneering work [Sha48]. Messages to be transmitted
are modeled as random processes and the systems developed in this model perform well in prac-
tice. For information hiding on the other hand, the relation between the model and its validity is
more involved. A message encrypted under a one-time pad, for example, is indistinguishable from
uniformly random bits and this method is perfectly secure according to our notion of security. But
no warden would allow the prisoners to exchange random-looking messages! Thus, the crucial issue
for the validity of a formal treatment of steganography is the accuracy of the model for real data.
Nevertheless, we believe that our model provides insight in steganography. We hope that it
can serve also as a starting point for further work to formalize active adversaries or computational
security. approach to information hiding with active adversaries is presented by
Ettinger [Ett98].) A first extension would be to model the covertext source as a stochastic process
and consider statistical estimation and decision techniques. Another idea would be to value the
possible decisions and use the methods of statistical decision theory [Ber85].
Related to this work is a paper by Maurer [Mau96] on unconditionally secure authentication
[Mas91, Sim91]. It shows how Simmons' bound [Sim85] and many other lower bounds in
authentication theory can be derived and generalized using the hypothesis testing approach. Another
information-theoretic approach to steganography is [ZFK
The paper is organized as follows. Hypothesis testing is presented in Section 2 from an
information-theoretic viewpoint. Section 3 contains the formal description of the model and the
security definition. In Section 4, we provide some examples of unconditionally secure stegosystems
and discuss the effects of data compression. A universal information hiding scheme that requires
no knowledge of the covertext statistics is presented in Section 5. It is based on a universal data
compression algorithm, which is similar to the well-known Lempel-Ziv algorithms [ZL77, BCW90].
Some extensions and conclusions are given in Section 6.
2 Review of Hypothesis Testing
We give a brief introduction to hypothesis testing and to information-theoretic notions (see [Bla87,
CT91]). Logarithms are to the base 2. The cardinality of a set S is denoted by jSj. The entropy
of a random variable X with probability distribution PX and alphabet X is defined as
The conditional entropy of X conditioned on a random variable Y is
denotes the entropy of the conditional probability distribution P XjY =y .
Hypothesis testing is the task of deciding which one of two hypotheses H 0 or H 1 is the true
explanation for an observed measurement Q [Bla87]. In other words, there are two possible probability
distributions, denoted by PQ0 and PQ1 , over the space Q of possible measurements. If H 0
is true, then Q was generated according to PQ0 , and if H 1 is true, then Q was generated according
to PQ1 . A decision rule is a binary partition of Q that assigns one of the two hypotheses to each
possible measurement q 2 Q. The two possible errors that can be made in a decision are called a
type I error for accepting hypothesis H 1 when H 0 is actually true and a type II error for accepting
true. The probability of a type I error is denoted by ff, the probability of a type II
error by fi.
A method for finding the optimum decision rule is given by the Neyman-Pearson theorem. The
decision rule is specified in terms of a threshold parameter T ; ff and fi are then functions of T . The
theorem states that for any given threshold T 2 R and a given maximal tolerable probability fi of
type II error, ff can be minimized by assuming hypothesis H 0 for an observation q 2 Q if and only
if
log PQ0 (q)
In general, many values of T must be examined to find the optimal decision rule. The term on the
left hand side in (1) is called the log-likelihood ratio.
The basic information measure of hypothesis testing is the relative entropy or discrimination
between two probability distributions PQ0 and PQ1 , defined as
(q) log PQ 0
The relative entropy between two distributions is always nonnegative and is 0 if and only if the distributions
are equal. Although relative entropy is not a true distance measure in the mathematical
sense because it is not symmetric and does not satisfy the triangle inequality, it can be useful to
think of it as a distance. The binary relative entropy d(ff; fi) is defined as
The following relation connects entropy, relative entropy, and the size of the alphabet for any
random variable X PU is the uniform distribution over X , then
Relative entropy and hypothesis testing are linked through the Neyman-Pearson theorem above:
The expected value of the log-likelihood ratio in (1) with respect to PQ 0
is equal to the relative
entropy D(PQ0 kPQ1 ) between PQ0 and PQ1 . The following standard result shows that deterministic
processing cannot increase the relative entropy between two distributions.
Lemma 1. Let PQ0 and PQ1 be probability distributions over Q. For any function f
Because deciding between H 0 and H 1 is a special form of processing, the type I and type II
error probabilities ff and fi satisfy
This bound is typically used as follows: Suppose that ffi is an upper bound on D(PQ0 kPQ1 ) and
that there is a given upper bound on the type I error probability ff. Then (4) yields a lower bound
on the type II error probability fi. For example, implies that fi - 2 \Gammaffi .
A similar result holds for a generalized hypothesis testing scenario where the distributions PQ 0
and PQ1 depend on knowledge of an additional random variable V . The probability distributions,
the decision rule, and the error probabilities are now parameterized by V . In other words, the
probability distributions are P Q0 jV =v and P Q1 jV =v for all v 2 V, the decision rule may depend on
the value v of V , and the error probabilities are ff(v) and fi(v) for each v 2 V. Let the average
type I and type II errors be
The conditional relative entropy between PX and P Y (over the same alphabet X ) conditioned
on a random variable Z is defined as
z2Z
It follows from the Jensen inequality and from (4) that
3 Model and Definition of Security

Figure

shows our model of a stegosystem. Eve observes a message that is sent from Alice to Bob.
She does not know whether Alice sends legitimate covertext C or stegotext S containing hidden
information for Bob. We model this by letting Alice operate strictly in one of two modes: either
she is active (and her output is S) or inactive (sending covertext C).
If Alice is active, she transforms C to contain an embedded message using a secret key K.
(Alternatively, Alice could also generate C herself.) Alice may use a private random source R for
embedding. The output of the hiding process is the stegotext S. Bob must be able to recover E
from his knowledge of the stegotext S and from the key K. Expressed in terms of entropy, the
system satisfies:
C or S
Channel
Secure
Alice Bob
Eve
Extracting
Key Generation
K K
Public Channel
Detection
R
Embedding

Figure

1: The model of a secret-key stegosystem with passive adversary. It shows the embedded
text E, the covertext C, the stegotext S, Alice's private random source R, and the secret key K
shared by Alice and Bob. Alice is either sending covertext C or stegotext S.
1. The stegotext is determined uniquely by Alice's inputs.
2. H(E) ? 0. There is uncertainty about the embedded message.
3. must be able to decode the embedded message uniquely.
If Alice is inactive, she sends covertext C and no embedding takes place. The embedding
mechanism, E, K, and R can be thought of as absent.
Repetition is not considered in this model; it encompasses everything sent from Alice to Bob.
For example, if Alice sends multiple messages to Bob and at least one of them contains hidden
information, she is considered active and S consists of the concatenation of all her messages.
The probability distributions are assumed to be known to all parties if not stated otherwise. In
addition, Bob knows whether Alice is active or not.
Eve, upon observing the message sent by Alice, has to decide whether it was generated according
to the distribution of the innocent covertext C or according to the modified distribution of the
stegotext S, i.e., whether Alice is active. Since this task is a hypothesis testing problem, we
quantify the security of a stegosystem in terms of the relative entropy distance between PC and
Definition 1. A stegosystem as defined above with covertext C and stegotext S is called ffl-secure
against passive adversaries if
D(PC
the stegosystem is called perfectly secure.
Consider Eve's decision process for a particular decision rule, given by a binary partition (C
of the set C of possible covertexts. She decides that Alice is active if and only if the observed message
c is contained in C 1 . Ideally, she would always detect a hidden message. (But this occurs only if
Alice chooses an encoding such that valid covertexts and stegotexts are disjoint.) If Eve fails to
detect that she observed stegotext S, she makes a type II error. Its probability is denoted by fi.
The opposite error, which usually receives less attention, is the type I error: Eve decides that
Alice sent stegotext although it was a legitimate cover message C; this probability is denoted by ff.
As a special case, one can assume that Eve never makes a type I error and accuses Alice of sending
hidden information when she is inactive Such a restriction could be imposed on Eve by
external mechanisms.
imposes a bound on the achievable error probabilities by Eve. From (4) we obtain
the following theorem.
Theorem 2. In a stegosystem that is ffl-secure against passive adversaries, the probability fi that
the adversary does not detect a hidden message and the probability ff that the adversary falsely
detects a hidden message satisfy
In particular, if
In a perfectly secure system we have D(PC kP S thus, Eve can
obtain no information about whether Alice is active by observing the message.
As an example, suppose Alice is given a digital image m that she is permitted to send to Bob.
Using a perceptional model, she has determined a set M of equivalent images that are visually
indistinguishable from m. Regardless of whether Alice is active or not, she will send a randomly
chosen element of M and this defines the probability space underlying C. Note that in our model,
the adversary knows at least M and possibly also m. Alice can use the techniques described below
for embedding information; however, to achieve robustness against active adversaries who modify
the image, more sophisticated coding methods are necessary (see e.g. [CKLS96]).
It may be the case that external events influence the covertext distribution; for example, news
reports or the local weather if we think of the prisoners' problem. This external information
is denoted by Y and known all participants. Our model and the security definition above can
be modified accordingly. The quantities involved will be conditioned on knowledge of Y and
we consider the average error probabilities
for the type I error and
for the type II error, where ff(y) and fi(y) denote the type I and type II error
probabilities for y, respectively.
The modified stegosystem with external information Y , covertext C, and stegotext S is called
ffl-secure against passive adversaries if
It follows from (6) that the average error probabilities satisfy d(ff; fi) - ffl, similar to Theorem 2.
In the next section, we show that perfectly secure stegosystems exist for particular sources
of covertext. We start with especially simple (or unrealistic) covertext distributions and then
consider arbitrary covertext statistics and the effects of data compression. A universal stegosystem
that includes data compression and does not rely on knowledge of the covertext distribution is
presented in Section 5.
Unconditionally Secure Stegosystems
The above model tells us that we obtain a secure stegosystem whenever the stegotext distribution is
close to the covertext distribution without knowledge of the key. The embedding function depends
crucially on knowledge about the covertext source. We assume first that the covertext distribution
is known and design corresponding embedding functions.
If the covertext consists of independent and uniformly random bits, then the one-time pad
provides a perfectly secure stegosystem. For completeness, we briefly describe this system formally.
Assume the covertext C is a uniformly distributed n-bit string for some positive n. The key
generator chooses the n-bit key K with uniform distribution and sends it to Alice and Bob. The
embedding function (if Alice is active) consists of the bitwise XOR of the particular n-bit message
e and K, thus and Bob can decode by computing K. The resulting stegotext S
is uniformly distributed in the set of n-bit strings and therefore D(PC kP S Thus, the one-time
pad provides perfect steganographic security if the covertext is uniformly random.
As a side remark, we note that this one-time pad system is equivalent to the basic scheme of
visual cryptography [NS95]. This technique hides a monochrome picture by splitting it into two
random layers of dots. When these are superimposed, the picture appears. It is also possible
to produce two innocent looking pictures such that both of them together reveal an embedded
message.
For general covertext distributions, we now describe a system that embeds a one-bit message
in the stegotext. The extension to larger message spaces is straightforward. Let the covertext C
with alphabet C have an arbitrary distribution PC . Alice constructs the embedding function from a
partition of C into two parts such that both parts are assigned approximately the same probability
mass under C. In other words, let
PC (c)
Alice and Bob share a one-bit key K 2 f0; 1g. Define C 0 to be the random variable with alphabet
equal to the conditional distribution P CjC2C 0
and define C 1 similarly over
Alice computes the stegotext to embed a message e 2 f0; 1g as
Bob can decode the message because he knows that only if S 2 CK .
Theorem 3. The one-bit message stegosystem described above isln 2
secure against passive adversaries.
Proof. Let We show only the case ffi ? 0. It is straightforward to verify
that
It follows that
D(PC
PC (c) log PC (c)
PC (c) log(1
using the fact that log(1 2.
A word on data compression techniques. Suppose the embedding as described above takes place
before compression is applied to S (or C). Data compression is a deterministic process. Therefore,
applies and shows that if we start with an ffl-secure stegosystem, the security of the
compressed system is also at most ffl. To put it another way, data compression can never hurt the
security of a stegosystem and make detection easier for the adversary.
5 Steganography with Universal Data Compression
The stegosystems described in Section 4 assume that the covertext distribution is known to all
parties. This seems not realistic for many applications. However, if we extend the model of a
stegosystem to stochastic processes and consider the covertext as an ergodic source, its distribution
can be estimated by observing the source output. This is precisely what universal data compression
algorithms do for the purpose of source coding. We now show how they can be modified for
information hiding.
Traditional data compression techniques, such as Huffman coding, require a priori knowledge
about the distribution of the data to be compressed. Universal data compression algorithms treat
the problem of source coding for applications where the source statistics are unknown a priori or
vary with time. A universal data compression universal algorithm achieves asymptotically optimal
performance on every source in some large class of possible sources. Essentially, this is accomplished
by learning the statistics of the data during operation as more and more data is observed. The
best known examples of universal data compression are the algorithms by Lempel and Ziv [ZL77,
We describe a universal data compression algorithm based on the concept of repetition times
due to Willems [Wil89], which is related to Elias' interval length coding [Eli87]. Then we modify the
algorithm to illustrate that a stegosystem can be constructed without knowledge of the covertext
distribution. The performance of Willems' algorithm is inferior to the Lempel-Ziv algorithms for
most practical data but it is simpler to describe and to analyze. We assume that covertext and
stegotext in the model according to Section 3 are stationary stochastic processes. This corresponds
to the ergodicity assumptions that are made for many data compression algorithms.
The Repetition Times Compression Algorithm: The algorithm is described for binary
sources but can easily be generalized to arbitrary alphabets. The parameters of the algorithm
are the blocklength L and the delay D. Consider a stationary binary source X producing fX t
with values in f0; 1g. The source output is divided into blocks Y
bits each. Encoding of a block Y t operates by considering its repetition time, the length of the
interval since its last occurrence. Formally, the repetition time \Deltat y of the block Y
\Deltat y and Y t\Gamma\Deltat y
the encoder outputs C (\Deltat y ), using a
particular variable-length encoding C of \Deltat y described below. If \Deltat y - 2 D , however, the block y is
retransmitted literally. The distinction between repetition time encoding and literal data is marked
by a single bit in the output stream.
Repetition time is encoded using the following code for integers between 1 and 2 D \Gamma 1. Let
l (k) denote binary representation of the integer k using l digits and let De. The encoding
C is
where k denotes the concatenation of the bit strings. Thus, C(t) contains first the binary length
of t encoded using fixed length d and then the remaining bits of t except for the most significant
bit. For initialization, a block y that occurs for the first time is encoded as if it had occurred at
\Gammay.
The encoder and decoder maintain a buffer of the last 2 D blocks of the source. In addition,
the encoder maintains an array indexed by L-bit blocks y that contains the position t y (modulo
last occurred (the time buffer). Encoding and decoding therefore take only a constant
number of operations per block. The formal analysis of the scheme [Wil89] using
that for L !1, the encoding rate (the average number of code bits per source word) converges to
the entropy rate of the source X.
The Modification for Information Hiding: The stegosystem based on Willems' algorithm
exploits the fact that the average repetition time of a block Y yields an estimate of its
probability since it will converge to P Y (y) \Gamma1 . If the block y is replaced with another block y 0 close
to y in average repetition time (and therefore in probability), the source statistics are only slightly
altered. Information is only hidden in blocks with low probability, as determined by a stego rate
parameter ae ? 2 \GammaD . Alice and Bob share an m-bit secret key K and Alice wants to hide an m-bit
message E.
Here, both the encoder and decoder maintain a time buffer indexed by blocks. In addition to
the index t of the last occurrence of block y, each entry contains also its average repetition time
\Deltat y and the number of its occurrences so far, n y . For each encoded block y with repetition time
\Deltat y , the average repetition time \Deltat y is replaced by (n y \Deltat y In addition, n y is
increased, but never beyond 2 D . Let r(y) denote the rank function of blocks that associates with
a block y the rank of \Deltat y , considering the current values of the average repetition times.
Information hiding takes place if the encoder or the decoder encounters a block y such that
\Deltat y - 1
ae (before updating buffers). If this is the case, bit j of the message m is embedded in y 0
according to
and encoding proceeds as before with y 0 replacing y. In other words, y 0 is either equal to y or to the
block immediately following y in the average repetition time ranking, depending on the embedded
bit. The decoder computes the average repetition times in the same way and can thus detect the
containing hidden information and decode E similarly.
Compared to data compression, the storage complexity of the encoding and decoding algorithms
is increased by a constant factor, but their computational complexity grows by a factor of about L
due to the maintenance of the ranking.
The resulting stegosystem achieves asymptotically perfect security since the distance between
the probabilities of the exchanged blocks vanishes. The formal statement of this will be given in
the full version of the paper.
6 Extensions
The presented information-theoretic model for steganography can be considered as one particular
example of a statistical model. We propose to consider also other approaches from statistical
decision theory. As noted before, an immediate extension would be to model the covertext source
as a stochastic process.
Simmons' original scenario of the prisoners' problem includes authentication, that is, the secret
shared by Alice and Bob can partially be used for authenticating Alice's messages. The
reason for this is that Alice and Bob want to protect themselves (and are allowed to do so) from
a malicious warden that tries to fool Bob into accepting fraudulent messages as originating from
Alice. This implies some changes to the model. Denote the part of the key used for authentication
by Z. Then, for every value z of Z, there is a different covertext distribution P CjZ=z induced by the
authentication scheme in use. However, since the adversary Eve does not know Z, the covertext
distribution to consider for detection is PC , the marginal distribution of PCZ . We note that this
model differs from the general scenario with an active adversary; there, the adversary succeeds if she
can destroy the embedded hidden information (as is the case in copyright protection applications,
for example). Here, the prisoners are only concerned about hiding information in messages that
may be authenticated to detect tampering.
As already mentioned in the Introduction, the assumption of a fixed covertext distribution
seems to render our model somewhat unrealistic for the practical purposes of steganography. But
what are the alternatives? Should we rather study the perception and detection capabilities of
human cognition since most cover data (text, sound, images) is ultimately intended for human
receivers? Viewed this way, steganography could fall entirely into the realms of image, audio, and
speech processing or artificial intelligence. However, it seems that the information-theoretic model
and other statistical approaches will ultimately be more useful for deriving statements about the
security of information hiding schemes-and a formal security notion is one of the main reasons for
introducing a mathematical model of steganography.

Acknowledgment

I am grateful to Victor Boyko, Mark Ettinger, Ron Rivest, and Michael Waidner for interesting
discussions on this subject.



--R

Information hiding
On the limits of steganography

Statistical decision theory and Bayesian analysis
Techniques for data hiding
Principles and practice of information theory
robust watermark for multimedia
Elements of information theory
Interval and recency rank source coding: two on-line adaptive variable-length schemes
Steganalysis and game equilibria
An introduction
A unified and generalized treatment of authentication theory
Advances in Cryptology: CRYPTO
Advances in Cryptology: EUROCRYPT
Information hiding terminology
Advances in Cryp- tology: EUROCRYPT '96 (Ueli Maurer
Advances in Cryp- tology: EUROCRYPT '97 (Walter Fumy
A mathematical theory of communication
The prisoners' problem and the subliminal channel
Authentication theory/coding theory
An introduction to shared secret and/or shared control schemes and their application
Universal data compression and repetition times
Modeling the security of steganographic systems
A universal algorithm for sequential data compression
--TR
Principles and practice of information theory
Text compression
Elements of information theory
Digital watermarking
Computers and Intractability
Information Theory
Provably Secure Steganography
Information Hiding Terminology - Results of an Informal Plenary Meeting and Additional Proposals
Modeling the Security of Steganographic Systems
Steganalysis and Game Equilibria
An Information-Theoretic Approach to Steganography and Watermarking
covert channel;universal data compression;perfect security;information hiding;one-time pad;subliminal channel