Information Technology Reference
In-Depth Information
10.1 Introduction
Message embedding is the science of covert and undetectable communica-
tions, which protects secret information from illegal access by third parties.
In contrast with cryptography, which encrypts the transmitted information
into meaningless form but can expose the secret information to detection
by malicious attackers, message embedding (so-called steganography) hides
secret information in a cover so that attackers find it difficult to judge whether
the hidden secret information exists or not. Message embedding was origi-
nally formulated as the “Prisoners' Problem” by Simmons [1]. Take the fol-
lowing scenario for example. Alice and Bob are prisoners in separate jail cells
far from each other who want to devise an escape plan. They are allowed to
exchange messages, but their communication is monitored by a warden, Eve,
who is always on the lookout for suspicious activity. Note that this scenario
involves a passive warden who observes the traffic but cannot interfere with
the communication. As a result, the prisoners can succeed in their escape if
they can exchange secret messages without arousing the warden's suspicion.
The prisoners resort to message embedding and embed the details of their
escape plan into innocuous looking objects. To embed a message, the sender
slightly modifies the cover object and then generates the stego object. The
main requirement of any message embedding system is statistical unde-
tectability. Thus, the prisoners' goal is to hide the details of the escape plan
so that warden Eve cannot tell whether the transmitted objects contain
embedded messages or not. The formal definition of this requirement in the
information-theoretic model was given by Cachin [2].
According to Kerckhoffs's principle, a cryptosystem should be secure even
if everything about the system, except the key, is public knowledge. In other
words, the security of a cryptosystem must depend solely on the key. Thus,
Alice and Bob must use a key, which is a secret shared between them, to
design their message embedding process. In general, the key is used to devise
the selection rule for identifying a subset of the cover objects that could con-
tain embedded messages. The placement of embedding changes in the cover
object is called the selection channel. To minimize the detectability of embed-
ded messages, the selection channel must be revealed as little as possible dur-
ing communication since this knowledge can aid the warden [3]. However, an
obvious problem at this point is that neither the warden nor the recipient know
the selection channel and are thus unable to read the embedded message.
The study of such nonshared selection channels is equivalent to writing
in a memory with defective cells [4,5]. The defective memory that is mod-
eled as a discrete memory-less channel is a special case of the informed
Gel'fand-Pinsker channel [6]. Heegard and El Gamal [7] studied storage
capacity based on the Gel'fand-Pinsker theory for computer memory with
defects. The message embedding technique in the passive warden's scenario
focuses on embedding for the noise-free case. We also consider message
