\documentclass{llncs}
\usepackage{amsmath}
\usepackage{amsfonts}

\makeatletter

\newcommand{\insec}[2]
 {\mbox{\bf InSec}^{\mbox{#1}}_{#2}}

\newcommand{\adv}[2]
 {\mbox{\bf Adv}^{\mbox{#1}}_{#2}}

\newcommand{\fail}[2]
 {\mbox{\bf Fail}^{#1}_{#2}}

\newcommand{\success}[2]
 {\mbox{\bf Succ}^{#1}_{#2}}

\newcommand{\DD}
 {\mathcal{C}}

\newcommand{\SE}
 {SE}

\newcommand{\SD}
 {SD}

\newcommand{\RS}
 {RS}  

\newcommand{\TR}[2]{#1}
%\newcommand{\TR}[2]{#2}


\TR{\usepackage{fullpage}}{}
\TR{\usepackage{cmu-titlepage}}{}

\newcommand{\WW}
 {\mathcal{W}}

\newcommand{\OO}
 {\mathcal{O}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
%\theoremstyle{plain}    
\spnewtheorem{thm}{Theorem}{\bfseries}{\it}
\spnewtheorem{cor}{Corollary}{\bfseries}{\it}
%\numberwithin{equation}{section} %% Comment out for sequentially-numbered
%\numberwithin{figure}{section} %% Comment out for sequentially-numbered
%\theoremstyle{definition}
\spnewtheorem{defn}{Definition}{\bfseries}{}
%\spnewtheorem{lemma}[thm]{Lemma}{\bfseries}{}
\spnewtheorem{cons}{Construction}{\bfseries}{}
\spnewtheorem*{defn*}{Definition}{\bfseries}{}
\newcommand{\comment}[1]{}

\TR{\abstract{Informally, {\it steganography} is the process of sending a secret
message from Alice to Bob in such a way that an eavesdropper (who
listens to all communications) cannot even tell that a secret message
is being sent. In this work, we initiate the study of steganography
from a complexity-theoretic point of view. We introduce definitions
based on computational indistinguishability and we prove that the
existence of one-way functions implies the existence of secure
steganographic protocols.}
  \keywords{Steganography, Cryptography, Provable Security}
  \trnumber{CMU-CS-02-149}
}{}
\makeatother

\begin{document}
\title{Provably Secure Steganography \TR{}{\\(Extended Abstract)}}
\author{Nicholas J. Hopper \and John Langford \and Luis von Ahn}
\institute{Computer Science Department, Carnegie Mellon University, Pittsburgh PA 15213, USA\\
\email{\{hopper,jcl,biglou\}@cs.cmu.edu}}
%\date{}
\maketitle

\TR{}
   {\renewcommand{\baselinestretch}{0.95}}

\TR{}
   {\begin{abstract}
       Informally, {\it steganography} is the process of sending a secret
       message from Alice to Bob in such a way that an eavesdropper (who
       listens to all communications) cannot even tell that a secret message
       is being sent. In this work, we initiate the study of steganography
       from a complexity-theoretic point of view. We introduce definitions
       based on computational indistinguishability and we prove that the
       existence of one-way functions implies the existence of secure
       steganographic protocols.
   \end{abstract}
   }

\section{Introduction}

The scientific study of steganography began in 1983 when Simmons
\cite{S83} stated the problem in terms of communication in a prison. In
his formulation, two inmates, Alice and Bob, are trying to hatch an escape
plan. The only way they can communicate with each other is through a
public channel, which is carefully monitored by the warden of the prison,
Ward. If Ward detects any encrypted messages or codes, he will throw both
Alice and Bob into solitary confinement. The problem of steganography is,
then: how can Alice and Bob cook up an escape plan by communicating over
the public channel in such a way that Ward doesn't suspect anything fishy
is going on.  (Notice how steganography is different from classical
cryptography, which is about hiding the {\it content} of secret messages:
steganography is about hiding the very existence of the secret messages.)

Steganographic ``protocols'' have a long and intriguing history that goes
back to antiquity. There are stories of secret messages written in
invisible ink or hidden in love letters (the first character of each
sentence can be used to spell a secret, for instance). More recently,
steganography was used by prisoners and soldiers during World War II
because all mail in Europe was carefully inspected at the time \cite{K67}.
Postal censors crossed out anything that looked like sensitive information
(e.g. long strings of digits), and they prosecuted individuals whose mail
seemed suspicious. In many cases, censors even randomly deleted 
innocent-looking
sentences or entire paragraphs in order to prevent secret
messages from going through. Over the last few years, steganography has
been studied in the framework of computer science, and several algorithms 
have been developed to hide secret messages in innocent looking data.

The main goal of this paper is to put steganography on a solid
complexity-theoretic foundation. We define steganographic secrecy in terms
of computational indistinguishability, and we define steganographic
robustness, which deals with the case of active wardens (ones that cross
out innocent-looking sentences or modify the messages just to prevent
secrets from going through). Our main result is a positive one: secret and
robust steganographic protocols exist within our model, given that one-way 
functions exist.

\subsection*{Related Work}

There has been considerable work on digital steganography.  The first
International Workshop on Information Hiding occurred in 1996, with
five subsequent workshops, and even books have been published about
the subject \cite{KP99}.  Surprisingly, though, very little work has
attempted to formalize steganography, and most of the literature
consists of heuristic approaches: steganography using digital images
\cite{\TR{J95,}{}KP99}, steganography using video systems
\TR{\cite{KP99,MT94,WW98}}{\cite{KP99}}, etc.
A few papers have given information theoretic models for steganography
\cite{C98,M00,OME98,ZF98}, but these are limited in the same way
that information theoretic cryptography is limited. We believe
complexity theory is the right framework in which to view
steganography and, to the best of our knowledge, this is the first
paper to treat steganography from a complexity-theoretic point of
view (and to achieve provably positive results). 

\subsection*{Organization of the Paper} 

In section \ref{sec-def} we define the basic cryptographic
quantities used throughout the paper, as well as the notions of a cover 
{\it channel} and a {\it stegosystem}. In section 
\ref{sec-secret} we define steganographic secrecy and
state protocols which are steganographically secret assuming the 
existence of one-way functions. In section \ref{sec-robust} we define robust steganographic
secrecy for adversaries with bounded power to perturb stegotext
messages and state protocols which satisfy this definition.
Section \ref{sec-discussion} closes the paper with a discussion
of implications.

\section{Definitions}
\label{sec-def}

\subsection{Preliminaries}

A function $\mu : \mathbb{N} \rightarrow (0,1)$ is said to be {\em
negligible} if for every $c > 0$, for all sufficiently large $n$,
$\mu(n) < 1/n^c$.
The concatenation of string $s_1 $ and string $s_2$ will be denoted by
$s_1 || s_2$, and  
when we write ``Parse $s$ as $s_1^t || s_2^t || \cdots || s_l^t$'' we mean
to
separate $s$ into strings $s_1,\ldots s_l$ where each $|s_i| = t$, $l
= \lceil |s| / t \rceil$, and $s = s_1 || s_2 || \cdots || s_l$.
We will 
let $U(k)$ denote the uniform distribution on $k$ bit strings, and 
$U(L,l)$ denote the uniform distribution on functions from $L$ bit
strings to $l$ bit strings. If $X$ is finite a set, we let $U(X)$ 
denote the uniform distribution on $X$. 

\subsection{Cryptographic notions}

Let $F : \left\{0,1\right\}^k \times \left\{0,1\right\}^L \rightarrow \left\{0,1\right\}^l$ denote a
family of functions.  Let $A$ be an oracle probabilistic adversary.
Define the
{\it prf-advantage of A over F} as
$$\adv{prf}{F}(A) = \left| \Pr_{K \leftarrow U(k), r \leftarrow \{0,1\}^*}[ A_r^{F_K(\cdot)}
= 1 ] -
 \Pr_{g \leftarrow U(L,l), r \leftarrow \{0,1\}^*}[ A_r^g = 1 ] \right|\ .$$ 
where $r$ is the string of random bits used by adversary $A$.
Define the insecurity of $F$ as $$\insec{prf}{F}(t,q) = \max_{A \in
\mathcal{A}(t,q)} \left\{\adv{prf}{F}(A)\right\}$$ where
$\mathcal{A}(t,q)$ denotes the set of adversaries taking at most $t$
steps and making at most $q$ oracle queries.  Then $F$ is a {\em
$(t,q,\epsilon)$-pseudorandom function} if $\insec{prf}{F}(t,q) \le
\epsilon$.  Suppose that $l(k)$ and $L(k)$ are polynomials.  A
sequence $\left\{F_k\right\}_{k \in \mathbb{N}}$ of families $F_k :
\left\{0,1\right\}^k \times \left\{0,1\right\}^{L(k)} \rightarrow
\left\{0,1\right\}^{l(k)}$ is called {\em pseudorandom} if for all
polynomially bounded adversaries $A$, $\adv{prf}{F_k}(A)$ is
negligible in $k$.  We will
sometimes write $F_k(K,\cdot)$ as $F_K(\cdot)$.

Let $E : \mathcal{K} \times \mathcal{R} \times \mathcal{P} \rightarrow
\mathcal{C}$ be a probabilistic private key encryption scheme, which
maps a random number and an $|m|$-bit plaintext to a ciphertext.
Consider a game in which an adversary $A$ is given access to an oracle
which is either:
\begin{itemize}
\item $E_K$ for $K \leftarrow U(\mathcal{K})$; that is, an
oracle which given a message $m$, uniformly selects random bits $R$
and returns $E_K(R,m)$; or

\item $g(\cdot) = U(|E_K(\cdot)|)$; that is, an oracle which on any query
ignores its input and returns a uniformly selected output of the
appropriate length.
\end{itemize}

Let $\mathcal{A}(t,q,l)$ be the set of adversaries $A$ which make $q$ 
queries
to the oracle of at most $l$ bits and run for $t$ time steps.  Define
the CPA advantage of $A$ against $E$ as

$$\adv{cpa}{E}(A) =\left| \Pr_{K \leftarrow
U(\mathcal{K}), s,r \leftarrow \{0,1\}^*}[A_r^{E_{K,s}} = 1] - 
\Pr_{g, r \leftarrow \{0,1\}^*}[A_r^{g} = 1]
\right|$$ 
where $E_{K,s}$ denotes $E_K$ with random bit source $s$. Define 
the insecurity of $E$ as
$$\insec{cpa}{E}(t,q,l) = \max_{A \in \mathcal{A}(t,q,l)}
\left\{\adv{cpa}{E}(A)\right\}\ .$$ Then $E$ is {\em
$(t,q,l,\epsilon)$-indistinguishable from random bits under chosen
plaintext attack} if $\insec{cpa}{E}(t,q,l) \le \epsilon$.  A sequence
of cryptosystems $\left\{E_k\right\}_{k \in \mathbb{N}}$ is called
{\em indistinguishable from random bits under chosen plaintext attack}
(IND\$-CPA) if for every PPTM $A$, $\adv{cpa}{E_k}(A)$ is negligible
in $k$.

Let $\DD$ be a distribution with finite support $X$.  Define the {\em
minimum entropy} of $\DD$, $H_\infty(\DD)$, as $$H_\infty(\DD) = \min_{x \in
X}\left\{ \log_2 \frac{1}{\Pr_{\DD}[x]} \right\}\ .$$

\subsection{Steganography}

Steganography will be thought of as a game between the warden, Ward,
and the inmate, Alice. The goal of Alice is to pass a secret message
to Bob over a communication channel (known to Ward). The goal of Ward
is to detect whether a secret message is being passed. In this and the
following sections we will formalize this game.  We start by defining
a communication channel.

\begin{defn*}
A {\em channel} is a distribution on bit sequences where each bit is
also timestamped with monotonically 
increasing time value.  Formally, a channel
is a distribution with support $(\{0,1\},t_1), (\{0,1\},t_2), ...,$
where $\forall i > 0: \,\,\, t_{i+1} \geq t_i $.
\end{defn*}

This definition of a channel is sufficiently general to encompass nearly
any form of communication.  It is important to note that our protocols
may depend upon the timing information as well as the actual bits sent
on a channel.  For example, it may be possible to do steganography
over email using only the timing of the emails rather than the
contents of the message.  It may also be possible for an enemy to
detect steganography via timing analysis.

Anyone communicating on a channel can be regarded as implicitly
drawing from the channel, so we will assume the existence of an oracle
capable of drawing from the channel.  In fact, we will assume
something stronger: an oracle that can \emph{partially} draw from the
channel a (finite, fixed length) sequence of bits.  This oracle can
draw from the channel in steps and at any point the draw is
conditioned on what has been drawn so far.  We let $\DD_h$ be the
channel distribution conditional on the history $h$ of already drawn
timestamped bits.  We also let $\DD_h^b$ be the marginal channel
distribution over the next block of $b$ timestamped bits conditional
on the history $h$.  Intuitively, $\DD_h^b$ is a distribution on the
next $b$ timestamped bits conditioned on the history $h$.  

Fix $b$. We
assume the existence of an oracle which can draw from $\DD_h^b$.  
We will call such a partial draw a ``block''.  
We
will require that the channel satisfy a minimum entropy constraint for
all blocks:
\[\forall h \mbox{ drawn from }\DD:\,\,\, H_\infty(\DD_h^b) > 1 \]
This partial draw will be conditional on all past draws and so we can
regard a sequence of partial draws as a draw from the channel.  This
notion of randomness is similar to Martingale theory where random
variable draws are conditional on previous random variable draws (and
we use Martingale theory in our analysis).

It is important to note that
a ``block'' might (for example) contain timestamped bits which
span multiple emails.  We will overload the definition of the
concatenation operator $||$ for sequences of timestamped bits.  Thus
$c_1||c_2$ will consist of the timestamped bits of $c_1$ followed by
the timestamped bits of $c_2$.

%%%% THIS IS ALL WELL AND GOOD BUT IT PUSHES US ONTO 13 PAGES
One example of a channel might be electronic mail.  We can map an email
system allowing communication from Alice to Bob to a channel by
considering all of the bits used to encode a \emph{particular} email
as a sequence of channel bits, each with the same timestamp.  The
timestamp of emailed bits would be the time of transmission.  The
complete channel consists of a distribution over sequences of
emails.

{\bf Remark.} In the remainder of this paper, we will assume that
cryptographic primitives remain secure with respect to an oracle which 
draws from a channel distribution $\DD_h^b$.  Thus channels which can be
used to solve the hard problems that standard primitives are based on must
be ruled out.  In practice this is of little concern, since the existence
of such channels would have previously led to the conclusion that the
primitive in question was insecure. 

\begin{defn} (Stegosystem)
A steganographic protocol, or stegosystem, is a pair of probabilistic
algorithms $S = (\SE,\SD)$.  $\SE$ takes a key $K \in
\left\{0,1\right\}^k$, a string $m \in \left\{0,1\right\}^\ast$ (the
{\em hiddentext}), a message history $h$, and an oracle $M(h)$ which
samples blocks according to a channel distribution
$\DD_h^b$. $\SE^M(K,m,h)$ returns a sequence of blocks $c_1 || c_2 ||
\ldots || c_l$ (the {\em stegotext}) from the support of $\DD_h^{l*b}$.
$\SD$ takes a key $K$, a sequence of blocks $c_1 || c_2 || \ldots
|| c_l$, a message history $h$, and an oracle $M(h)$, and returns a
hiddentext $m$. There must be a polynomial $p(k) > k$ such that $\SE^M$ and $\SD^M$ also satisfy the relationship:
\[ \forall m, |m| < p(k):\,\,\,\,\Pr(\SD^M(K,\SE^M(K,m,h),h) = m) \geq \frac{2}{3}
\]
where the randomization is over any coin tosses of $\SE^M$, $\SD^M$, and $M$.
(In the rest of the paper we will use $(\SE$,$\SD)$ instead of
$(\SE^M$,$\SD^M)$.)

\end{defn}

Note that we choose a probability of failure for the stegosystem of
$1/3$ in order to include a wide range of possible stegosystems.  In
general, given a protocol with any reasonable probability of failure,
we can boost the system to a very low probability of failure using
error-correcting codes. 

Although all of our oracle-based protocols will work with the oracle
$M(h)$, we will always use it in a particular way.  Consequently, it
will be convenient for us to define the rejection sampling function
$RS^{M, F} :
\{0,1\}^{*} \times \mathbb{N} \rightarrow \{0,1\} $.
\begin{center}
\begin{minipage}[t]{3in}
\begin{tabbing}
{\bf Procedure} ${\tt RS}^{M,F}$: \\
{\bf Input:} target $x$, iteration $count$ \\
i = 0 \\
re\=peat: $c \leftarrow M$; increment i \\
until $F(c) = x$ or $i$ = $count$ \\
{\bf Output:} $c$
\end{tabbing}
\end{minipage}
\end{center}
The function $RS$  simply samples from the
distribution provided by the sample oracle $M$ until $F(M) = x$.  The
function will return $c$ satisfying $F(c) = x$ or the $count$-th
sample from $M$.  Note that we use an iteration count to bound the
worst case running time of $RS$ and that $RS$ may fail to return a $c$
satisfying $F(c)=x$.

{\bf Comment.} We have taken the approach of assuming a channel which
can be drawn from freely by the stegosystem; most current proposals
for stegosystems act on a single sample from the channel (one
exception is \cite{C98}).  While it may be possible to define a
stegosystem which is steganographically secret or robust and works in
this style, this is equivalent to a system in our model which merely
makes a single draw on the channel distribution.  Further, we believe
that the lack of reference to the channel distribution may be one of
the reasons for the failure of many such proposals in the literature.

It is also worth noting that we assume that a stegosystem has very
little knowledge of the channel distribution---$\SE$ and $\SD$ may only
\emph{sample} from an oracle according to the distribution.  This is because
in many cases the full distribution of the channel has never been
characterized; for example, the oracle may be a human being, or a
video camera focused on some complex scene.  However, our definitions
do not rule out encoding procedures which have more detailed knowledge 
of the channel distribution.

Sampling from $\DD_h^b$ might not be trivial. In some cases $M(h)$ is a
human, and in others a simple randomized program.  We stress that it
is important to minimize the use of such an oracle, because oracle
queries can be extremely expensive. In practice, this oracle is also
the weakest point of all our constructions. We assume the existence of
a {\it perfect} oracle: one that can perform independent draws, one
that can be rewound, etc. This assumption can be justified in some
cases, but not in others. If the oracle is a human, the human may not
be able to perform independent draws from the channel as is required by 
the
function $RS$. A real world Warden would use this to his advantage. We
therefore stress the following cautionary remark: {\it our protocols
will be shown to be secure under the assumption that the oracle is
perfect}.

Finally, we mention that our decoding algorithm, $SD$, is defined to
have access to the oracle $M(h)$. This is a general definition, and
there are cases in which this access will not be necessary. Protocols
in which $SD$ needs no access to $M(h)$ are clearly preferred.

\section{Steganographic Secrecy}
\label{sec-secret}

A \emph{passive} warden, $W$, is an adversary which plays the
following game:
\begin{enumerate}
\item $W$ is given access to an oracle $M(h)$ which samples blocks
(one at a time) from the distribution $\DD_h^b$, for past histories $h$
drawn from the channel.  $W$ makes as many draws from $M(h)$ as it
likes.

\item $W$ is given access to a second oracle which is either
$\SE(K,\cdot,\cdot)$ or $O(\cdot, \cdot)$ defined by $O(m,h) \leftarrow
\DD_h^{|\SE(K,m,h)|}$. Ward $W$ makes at most $q$ queries totaling $l$
bits (of hiddentext) to this oracle.

\item $W$ outputs a bit.
\end{enumerate}
We define $W$'s advantage against a stegosystem $S$ by
$$\adv{ss}{S,\DD}(W) = \left| \Pr_{K,r,M,SE}[W_r^{M,\SE(K,\cdot,\cdot)} = 
1] 
- \Pr_{r, M, O}[W_r^{M,O(\cdot,\cdot)} = 1] \right|\ ,$$ where the warden
uses random bits $r$. Define the insecurity of $S$ by
$$\insec{ss}{S,\DD}(t,q,l) = \max_{W \in \mathcal{W}(t,q,l)}
\left\{\adv{ss}{S,\DD}(W)\right\}\ ,$$ where $\mathcal{W}(t,q,l)$
denotes the set of all adversaries which make at most $q$ queries
totaling at most $l$ bits (of hiddentext) and running in time at most $t$.

\begin{defn} (Steganographic secrecy)
A Stegosystem $S = (\SE,\SD)$ is called {\em $(t,q,l,\epsilon)$
steganographically secret against chosen hiddentext attack} for the channel $\DD$
($(t,q,l,\epsilon)$-SS-CHA-$\DD$) if $\insec{ss}{S,\DD}(t,q,l) \le
\epsilon$.
\end{defn}

\begin{defn} (Universal Steganographic Secrecy)
A Stegosystem $S$ is called {\em $(t,q,l,\epsilon)$-universally
steganographically secret against chosen hiddentext attack} ($(t,q,l,\epsilon)$-USS-CHA) if it is
$(t,q,l,\epsilon)$-SS-CHA-$\DD$ for every channel distribution $\DD$ that
satisfies $H_\infty(\DD_h^b) > 1$ for all $h$ drawn from $\DD$.  A sequence
of stegosystems $\left\{S_k\right\}_{k \in \mathbb{N}}$ is called {\em
universally steganographically secret} if for every channel 
distribution $\DD$ and for every PPTM $W$,
$\adv{ss}{S_k,\DD}(W)$ is negligible in $k$.
\end{defn}

Note that steganographic secrecy can be thought of roughly as encryption
which is indistinguishable from {\em arbitrary} distributions $\DD$.  

\subsection{Construction: Stateful Universal Steganographic Secrecy}

We now show a stateful protocol which is universally steganographically 
secret.
This protocol is not new and can
be found (up to small differences) in \cite{AP98}, for instance.  The 
novel aspect is the proof of
steganographic secrecy within our model.


Assume Alice and Bob share a channel and let $\DD$ denote the channel
distribution.  We let $M(h)$ be an oracle which draws blocks (one at a
time) from the conditional distribution $\DD_h^b$.  Let
$F_K(\cdot,\cdot)$ denote a pseudorandom function family indexed by $k
= |K|$ key bits which maps a pair consisting of a $d$-bit number and
$b$ timestamped bits to the set $\left\{0,1\right\}$, i.e.,
$F:\{0,1\}^k\times\{0,1\}^d\times(\{0,1\},t)^b\rightarrow\{0,1\}$.
Let Alice and Bob share a secret key $K \in \left\{0,1\right\}^k$ and
a synchronized $d$ bit counter $N$.  Let $Enc$ and $Dec$ be the
encoding and decoding procedures, respectively, for an
error-correcting code which corrects up to a $\mu(k)$ fraction of
errors (where $\mu(k)$ is defined below) and which has stretch
function $\ell(\cdot)$. The following procedures allow Alice and Bob
to encode and decode a hiddentext and to send it via their shared
channel.


\begin{cons} \label{cons:nohash} (Steganographic Secrecy)  \end{cons}
\begin{center}
\begin{minipage}[t]{3in}
\begin{tabbing}
{\bf Procedure} {\tt S\ref{cons:nohash}.Encode}: \\
{\bf Input:} key $K$, hiddentext $m'$, history $h$ \\
Let $m = Enc(m')$ \\
Parse $m$ as $m_1^1 || m_2^1 || \cdots || m_l^1$\\
for \= $i = 1 \ldots l$ do \+ \\
$c_i \leftarrow RS^{M(h), F_K(N,\cdot)}(m_i, |K|)$ \\
set $h = h || c_i$ \\
increment $N$ \-\\
{\bf Output:} $c_1 || c_2 || \ldots || c_l$ 
\end{tabbing}
\end{minipage} \hspace{0.25in} \vline \hspace{0.25in}
\begin{minipage}[t]{3in}
\begin{tabbing} 
{\bf Procedure} {\tt S\ref{cons:nohash}.Decode}: \\
{\bf Input:} key $K$, Stegotext $c$ \\
Parse $c$ as  $c^b_1 || c^b_2 || \ldots || c^b_l$ \\
for \= $i = 1 \ldots l$ do \+ \\
set $m_i = F_K(N,c_i)$ \\
increment $N$ \- \\
let $m = m_1 || m_2 || \cdots ||m_l$ \\
{\bf Output:} $Dec(m)$ 
\end{tabbing}
\end{minipage}
\end{center}
The idea behind this construction is simple. First, the encoding algorithm
splits the hiddentext $m$ into single bits. Then it draws blocks from
the channel until it finds $c_1$ such that $F_K(N,c_1)=m_1$. After
that it finds $c_2$ such that $F_K(N+1,c_2)=m_2$, and $c_3$, and so
on. This continues until all bits of $m$ have been encoded. The decoding 
algorithm simply applies $F_K(N+i-1,\cdot)$ to all the $c_i$'s. 

Note that the encoding procedure actually has a small probability of
failure per bit. In particular, $RS$ might not return a $c_i$ such
that $F_K(N+i-1,c_i)=m_i$, because $RS$ ``gives up'' after $|K|$
timesteps.  The probability of failure is dependent on the sampling
oracle $M$ and the evaluation oracle $F$.  

\begin{lemma} \label{th-error} If $\DD_h^b$ has minimum entropy 
at least $H$ and $|K|=k$, the probability of failure of $RS$ is bounded 
above by
$\mbox{fail}(k,\DD_h^b)+\insec{prf}{F}(O(kl), kl)$, where
$$
\mbox{fail}(k,\DD_h^b) \leq \sum_{j=0}^{2^H}\frac{{2^H \choose 
j}}{2^{2^{H}}}\left(\frac{j}{2^H}\right)^{k}
$$
\end{lemma}

\begin{proof}
\TR{
If $F$ were a truly random
function and the oracle had minimum entropy at least $H$ we would have
that the probability of failure of $RS$ would be bounded above by:
$$
\mbox{fail}(k,U) = \sum_{j=0}^{2^H}\frac{{2^H \choose 
j}}{2^{2^{H}}}\left(\frac{j}{2^H}\right)^{k}
$$
\noindent where $U$ is a uniform distribution on $2^H$ elements. 
This is because any distribution with minimum entropy $H$ can be 
described
as a convex combination of uniform distributions on $2^H$ elements.
Pick a fixed uniform distribution over $2^H$ elements.  The formula
gives the probability that there exists a bit, $m_i$, of hiddentext in
which all $|K|$ draws from the oracle result in a block $c$ with
$F(c)\neq m_i$: the probability is calculated by conditioning on
$j=|\{F(c)\neq m_i:c$ is a block$\}|$. Now, if $Z=aX+(1-a)Y$ is a mixture
of distributions then (by induction on $k$):
\begin{eqnarray*}
\mbox{fail}(k,Z) & = &\mbox{fail}(k-1,Z)\mbox{fail}(1,Z)\\
& \leq & 
[a\mbox{fail}(k-1,X)+(1-a)\mbox{fail}(k-1,Y)][a\mbox{fail}(1,X)+(1-a)\mbox{fail}(1,Y)]\\ 
& = &
a^2\mbox{fail}(k,X)+a(1-a)\mbox{fail}(k-1,X)\mbox{fail}(1,Y)+(1-a)^2\mbox{fail}(k,Y)
\\ & & +a(1-a)\mbox{fail}(k-1,Y)\mbox{fail}(1,X)\\
& = & 
a^2\mbox{fail}(k,X)+a(1-a)\mbox{fail}(1,X)^{k-1}\mbox{fail}(1,Y)+(1-a)^2\mbox{fail}(k,Y)
\\ & & +a(1-a)\mbox{fail}(1,Y)^{k-1}\mbox{fail}(1,X)\\
& \leq & 
a^2\mbox{fail}(k,X)+a(1-a)\mbox{fail}(1,X)^{k}+(1-a)^2\mbox{fail}(k,Y)
\\ & & +a(1-a)\mbox{fail}(1,Y)^{k}\\
& = & 
a\mbox{fail}(k,X)+(1-a)\mbox{fail}(k,Y)
\end{eqnarray*}
where the second inequality follows from $\forall x,y \in R\,\,\, 2xy
\leq x^2 + y^2$.

Inductively, we get: $\mbox{fail}(k,\DD_h^b)\leq \mbox{fail}(k,U)$.
In practice $F$ is {\it not} a random function, but rather a
pseudorandom function so the probability of failure of RS is bounded
above by $\mbox{fail}(k,\DD_h^b)+\insec{prf}{F}(O(kl), kl)$.  }{See the 
full version of the paper
\cite{HLvA02}.}

\end{proof}

It can be verified that $\mbox{fail}(k,\DD_h^b)$ is exponentially
small in $|K|$ and $H$. We will choose our error-correcting code to
correct a $\mu(k) = (1+\epsilon) *
\mbox{fail}(k,U(1))$ fraction of errors (note that $U(1)$ has minimum 
entropy 1). A Chernoff bound will then suffice to
show that the probability of decoding failure is exponentially small
in $l$.  For a channel $\DD^b_h$ with minimum entropy $1$, we have
$\mbox{fail}(k,\DD^b_h) \approx \frac{1}{4}$.  Consequently, we will at
worst require a code with a stretch function $\ell(n)$ approximately $2n$.  We will
assume for simplicity that the running times of $Enc$ and $Dec$ are
linear.

\begin{thm} \label{th-ss} Let $k$ = $|K|$. For any $l\leq 2^d$:
$$\insec{ss}{S\ref{cons:nohash},\DD}(t,q,l) \le \insec{prf}{F}(t + O(k\ell(l)), 
k\ell(l))$$
\end{thm}
\begin{proof}
For any warden, $W$, running in time $t$ and making $q$ queries totaling $l$ bits, we 
construct a corresponding PRF adversary $A$, where 
$$\adv{ss}{S\ref{cons:nohash},\DD}(W) =
\adv{prf}{F}(A)$$ The running time of $A$ is the running time of
warden $W$ plus the time of rejection sampling ($RS$): $O(k\ell(l))$ in the
worst case.  The number of calls to the sampling oracle, $M(h)$, is at
most $k\ell(l)$.

$A^f$ simply runs $W$, emulating the encoding procedure {\tt
S\ref{cons:nohash}.Encode} using the function oracle $f$ in place of
$F_K(\cdot,\cdot)$.  
Note that when $f$ is a uniformly chosen random
function, the output of $RS^{M(h),f}(\cdot, k)$ is
distributed identically to the channel distribution $\DD_h^b$. 
Similarly, when
$f$ is chosen from $F_K(\cdot,\cdot)$, the output of 
$RS^{M(h),f}(\cdot, k)$
is distributed identically to the output of
Construction~\ref{cons:nohash}, by the definition of the construction.
So the advantage is:
\begin{eqnarray*}
 \adv{prf}{F}(A) 
& = & \left| \Pr_{K \leftarrow U(k),r \leftarrow \{0,1\}^*}[
A_r^{F_K(\cdot,\cdot)} = 1 ] - \Pr_{g, r \leftarrow \{0,1\}^*}[ A_r^g = 1 ] \right|\ \\
& = & \left| \Pr_{K,r,M,SE}[W_r^{M,\SE(K,\cdot,\cdot)} = 1] -  
\Pr_{r,M,O}[W_r^{M,O(\cdot,\cdot)} = 1] \right|\ \\
& = & \adv{ss}{S\ref{cons:nohash},\DD}(W)
\end{eqnarray*}

And the theorem follows by the definition of insecurity.
\end{proof}

\begin{cor}
If $F_K(\cdot,\cdot)$ is pseudorandom then
construction~\ref{cons:nohash} is universally steganographically
secret against chosen-hiddentext attacks.
\end{cor}

\TR{\begin{proof}
$F_K(\cdot,\cdot)$ pseudorandom implies that for all polynomially
bounded adversaries $A$, $\adv{prf}{F_k}(A)$ is negligible in $k$.
The definition of insecurity and theorem \ref{th-ss} implies that for
any cover channel, $\DD$, the advantage of a warden will be negligible
in $k$. This, in turn, implies the corollary.
\end{proof}}{}

\subsection{Stateless Universal Steganographic Secrecy}

The following protocol also satisfies our definition for universal
steganographic secrecy. \TR{}{The proofs are omitted due to space
considerations, but are similar to the proof of Theorem~\ref{th-ss} in
the previous section, and can be found in the full version of the paper}  
Once again, this protocol (up to small
differences) is not new and can be found in \cite{AP98}; an
information theoretic version of the protocol can also be found in
\cite{C98}. 


We will say that a function $f : D \rightarrow R$ is an {\em unbiased
function on a distribution $\DD$} if for all $r \in R, h$, $\Pr_{d
\leftarrow \DD_h^b}[f(d) = r] = \frac{1}{|R|}$.
Let $f : (\left\{0,1\right\},t)^b \rightarrow \left\{0,1\right\}$ be a
public function which is unbiased on $\DD$.  Let
$E_K(\cdot,\cdot)$ and $D_K(\cdot)$ denote the encryption and
decryption functions for a cryptosystem which is indistinguishable
from random bits under chosen plaintext attack (i.e., IND\$-CPA) \cite{RBBK01}.  Suppose Alice 
and Bob
share a key $K \in \left\{0,1\right\}^k$.  The following procedures
allow encoding and decoding of messages in a manner which is
steganographically secret under chosen hiddentext attack for the
channel distribution $\DD$.  

\begin{cons} \label{cons:hash} (Stateless Steganographic Secrecy) 
\end{cons}

\begin{center}
\begin{minipage}[t]{3in}
\begin{tabbing}
{\bf Procedure} {\tt S\ref{cons:hash}.Encode}: \\
{\bf Input:} key $K$, hiddentext $m$, history $h$ \\
Let $s = E_K(m)$\\
Parse $s$ as $s_1^1 || s_2^1 || \cdots || s_l^1$\\
for \= $i = 1 \ldots l$ do \+ \\
$c_i \leftarrow RS^{M(h), f(\cdot)}(s_i,|K|)$ \\
set $h = h || c_i$ \-\\
{\bf Output:} $c_1|| c_2|| \ldots|| c_l$ 
\end{tabbing}
\end{minipage} \hspace{0.25in} \vline \hspace{0.25in}
\begin{minipage}[t]{3in}
\begin{tabbing} 
{\bf Procedure} {\tt S\ref{cons:hash}.Decode}: \\
{\bf Input:} key $K$, Stegotext $c$ \\
Parse $c$ as  $c^b_1 || c^b_2 || \ldots || c^b_l$ \\
for \= $i = 1 \ldots l$ do \+ \\
set $s_i = f(c_i)$ \- \\
set $s = s_1 || s_2 || \cdots || s_l$.\\
{\bf Output:} $D(K,s)$ 
\end{tabbing}
\end{minipage}
\end{center}

Note that the execution time for $SD$ is essentially linear in
\( l \) and the execution time for $SE$ is an expected \( O(l)
\).  Also note that our assumption of an unbiased function implies
that an error correcting code as in construction \ref{cons:nohash} is
unnecessary: the probability of failure here is $l/2^{|K|}$. Clearly,
the assumption of an unbiased $f$ is quite strong.  In practice, 
perfect unbiasedness may be hard to meet and stronger assumptions may
be required.  For example, when $f$ is a pseudorandom function, under
the assumption of a large minimum entropy in the channel, $f$ will be
nearly unbiased.

\begin{lemma} \label{thm:hash-adv}
For any warden $W \in \WW(t,q,l)$, we can construct
a corresponding adversary $A$ where $$\adv{ss}{S\ref{cons:hash},\DD}(W) =
\adv{cpa}{E}(A)\ .$$ The running time of $A$ is at most $t + O(kl)$, and
$A$ makes $q$ encryption queries for a total of $l$ bits of plaintext.
\end{lemma}

\TR{\begin{proof}
We are given a program $W$ for distinguishing between the output of
construction~\ref{cons:hash} and the ordinary traffic of the
channel, and an oracle for sampling blocks from that channel. We
construct a program $A$ which plays the CPA game --- 
distinguishing an $E_K(R,\cdot)$ oracle from a uniform $g$ oracle
--- with the same advantage as $W$.  $A$ simply runs the
encoding procedure {\tt
S\ref{cons:hash}.Encode} using its oracle in place of
$E_K(R,\cdot)$. Consider the following two cases:
\begin{itemize}
\item $O(m) = E_K(m)$.  Then the stegotexts output by the encoding
procedure will be identically distributed to stegotexts resulting from
the normal use of construction~\ref{cons:hash}.

\item $O(m) = g(m)$ is chosen uniformly from strings of appropriate length.
Then the stegotexts output by the encoding procedure will be
identically distributed to a history-dependent sample from the channel
distribution $\DD_h^b$.  This follows by the fact that $f$ is unbiased on
$\DD$ and the parsed substrings $g(m)_i$ are uniformly distributed
on $\left\{0,1\right\}$.
\end{itemize}

Thus $A$ can simply use the decision of $W$ to gain advantage
identical to that of $W$. More formally, 

\begin{eqnarray*}
 \adv{cpa}{E}(A) 
& = & \left| \Pr_{K \leftarrow U(k), s,r \leftarrow \{0,1\}^*}[
A_r^{E_{K,s}} = 1 ] - \Pr_{g, r \leftarrow \{0,1\}^*}[ A_r^g
= 1 ] \right|\ \\
& = & \left| \Pr_{K,r,SE,M}[ W_r^{M,SE(K,\cdot,\cdot)} = 1 ] - \Pr_{O,r,M}[
W_r^{M,O(\cdot,\cdot)} = 1 ] \right|\ \\
& = & \adv{ss}{S\ref{cons:hash},\DD}(W)
\end{eqnarray*}
\end{proof}}{}

\begin{thm} \label{thm:hash}
$\insec{ss}{S\ref{cons:hash},\DD}(t, q, l) \le
\insec{cpa}{E}(t + O(kl), q, l).$
\end{thm}

\TR{\begin{proof}
The theorem follows from Lemma~\ref{thm:hash-adv} and the definition
of insecurity.
\end{proof}}{}

\noindent {\bf Generalization.} The assumption that the balanced function, 
$f$, is unbiased can be
weakened to the assumption of an $\epsilon$-biased function where the
probability of any value is within $\epsilon$ of uniform.  The
same proofs work with the insecurity increased by at most $\epsilon$ 
(however, error correcting codes might be necessary in this case).

A few easy corollaries follow from Theorem~\ref{thm:hash}.  If $E$ is
indistinguishable from random bits under chosen plaintext attack then
construction~\ref{cons:hash} is SS-CHA-$\DD$ secure.  Additionally, if
$E$ is replaced by a public key cryptosystem which is
indistinguishable from random bits under chosen plaintext attack, then
construction~\ref{cons:hash} is a public key stegosystem which is
steganographically secret under chosen hiddentext attack (under an
appropriate generalization of our definitions to a public-key
scenario).


\section{Robust Steganography}
\label{sec-robust}

\subsection{Definitions for Robust Steganography}

Robust steganography will be modelled as a game between Alice and Ward
in which Ward is allowed to make some alterations to Alice's messages.
Alice wins if she can pass a message with high probability, even when
Ward alters her message.  For example, if Alice passes a single bit
per channel message and Ward is unable to change the bit with
probability at least $\frac{1}{2}$, Alice can use error correcting
codes to reliably transmit her message. It will be important to state
the limitations we impose on Ward, since otherwise he can replace all
messages with a new draw from the channel distribution, effectively
destroying any hidden information.  In this section we give a formal
definition of robust steganography with respect to a limited
adversary.  

We will model Ward's power as defined by a relation $R$ which is
constrained to not corrupt the channel too much.  This general notion
of constraint is sufficient to include many simpler notions such as
(for example) ``only alter at most 1\% of the bits''.

Let $\mathcal{D}$ be a finite distribution with support $X$ and let
$R$ be a relation between the set $X$ and the set $Y$ such that for
every $x \in X$, there exists a $y \in Y$ where $(x,y) \in
R$. Consider a single-player game of chance which is played as
follows:
\begin{enumerate}
\item The player draws $x$ according to $\mathcal{D}$.
\item The player chooses an arbitrary $y$ such that $(x,y) \in R$.
\item The player makes an independent draw $x'$ from $\mathcal{D}$.
\end{enumerate}
The player wins if $(x',y) \in R$.  Define the {\em obfuscation probability} of $R$ for $\mathcal{D}$ by 
$$\OO(R,\mathcal{D}) = \max_{y} \sum_{(x',y) \in R}
\Pr_{\mathcal{D}}[x']\ .$$ 

This function represents an upper bound on the player's winning
probability.  In particular, for any $y$ the player chooses in step 2,
$\OO(R,\mathcal{D})$ bounds the probability $\sum_{(x',y) \in R}
\Pr_{\mathcal{D}}[x']$ of winning.  Note that the $\log_2
\OO(R,\mathcal{D})$ gives the minimum amount of conditional
information retained about draws from $\mathcal{D}$ when they are
substituted arbitrarily amongst possibilities which satisfy $R$.  The
obfuscation probability is therefore a worst-case conditional entropy
(just as minimum entropy is a worst-case entropy), except that
logarithms have been removed.

Now let $R$ be an efficiently computable relation on blocks and let
$R(x) = \left\{ y : (x,y) \in R\right\}$.  We say that the pair
$(R,\DD_h^b)$ is $\delta$-admissible if $\OO(R,\DD_h^b) \le \delta$
and a pair $(R,\DD)$ is $\delta$-admissible if $\forall h \,\,\,
(R,\DD_h^b)$ is $\delta$-admissible.  An $R$-bounded active warden $W$
can be thought of as an adversary which plays the following game
against a stegosystem $S = (\SE,\SD)$:
\begin{enumerate}
\item $W$ is given oracle access to the channel distribution $\DD$ and 
makes as many draws as it likes.
\item $W$ is given oracle access to $\SE(K,\cdot,\cdot)$, and makes at most $q$ queries 
totaling at most $l_1$ bits to $\SE$.
\item $W$ presents an arbitrary message $m \in
\left\{0,1\right\}^{l_2}$ and history $h$.
\item $W$ is then given a sequence of blocks $c = c_1|| c_2|| \ldots||
c_u$ from the support of $\DD_h^{(u*b)}$, and returns a sequence $c' =
c_1'||c_2'||\ldots||c_u'$ where $c_i' \in R(c_i)$ for each  $1 \le i \le u$.  
Here $u$ is the number of blocks of stegotext output by $\SE(K,m,h)$.
\end{enumerate}

Define the success of $W$ against $S$ by $$\success{R}{S}(W) = \Pr_{K\leftarrow U(k), r\leftarrow \{0,1\}^*, o \leftarrow \{0,1\}^*}[\SD_o(K,W_r(\SE_o(K,m,h)),h) \ne m]$$
Here, $r$ and $o$ are the random bits used by Ward and the protocol, 
respectively.
Define the failure rate of $S$ by $$\fail{R}{S}(t,q,l) = \max_{W \in
\WW(R,t,q,l)}\left\{ \success{R}{S}(W) \right\}\ ,$$  where $\WW(R,t,q,l)$ denotes the
set of all $R$-bounded active wardens that submit at most $q$ queries
of total length at most $l_1$, produce a plaintext of length at most
$l_2 = l - l_1$ and run in time at most $t$. 


\begin{defn} (Robust Steganography)
A stegosystem $S = (\SE,\SD)$ is called {\em $(t,q,l,\epsilon,\delta)$
steganographically robust against R-bounded adversaries} for
the distribution $\DD$ (denoted $(t,q,l,\epsilon,\delta)$-SR-CHA-$(\DD,R)$) if the following conditions
hold:
\begin{itemize}
\item (Secrecy): $S$ is $(t,q,l,\epsilon)$-SS-CHA-$\DD$.
\item (Robustness): $\fail{R}{S}(t,q,l) \le \delta$.
\end{itemize}
A stegosystem is called {\em $(t,q,l,\epsilon,\delta)$ steganographically robust} (SR-CHA) if it is
$(t,q,l,\epsilon,\delta)$-SR-CHA-$(\DD,R)$ for every $\delta$-admissible
pair $(\DD,R)$.
\end{defn}

\begin{defn}(Universal Robust Steganography)
A sequence of stegosystems $\left\{S_k\right\}_{k \in \mathbb{N}}$ is
called {\em universally steganographically robust} if it is
universally steganographically secret and there exists a polynomial
$q(\cdot)$ and a constant $\delta \in [0,\frac{1}{2})$ such that for every PPTM
$W$, every $\delta$-admissible $(R,\DD)$, and all sufficiently large $k$,
$\success{R}{S_k}(W) < 1/q(k)$.
\end{defn}

\subsection{Universally Robust Stegosystem}

In this section we give a stegosystem which is Steganographically
robust against any bounding relation $R$, under a slightly modified
assumption on the channel oracles, and assuming that Alice and Bob
know some efficiently evaluable, $\delta$-admissible relation $R'$
such that $R'$ is a superset of $R$. For several reasons, this
stegosystem appears impractical but it serves as a proof that robust
steganography is possible for any admissible relation.

Suppose that the channel distribution $\DD$ is efficiently sampleable,
that is, there is an efficient algorithm $M$ which, given a uniformly
chosen string $s \in \{0,1\}^m$ and history $h$ produces a block
distributed according to $\DD_h^b$ (or statistically close to
$\DD_h^b$).  We will assume that Alice, Bob, and Ward all have access
to this algorithm.  Furthermore, we assume Alice and Bob share a key
$K$ to a pseudorandom function; and have a synchronized counter $N$.
Let $n$ be a robustness parameter.

\begin{cons} \label{cons:urobust} (Universally Robust Steganography) \end{cons}

\begin{center}
\begin{minipage}[t]{2.75in}
\begin{tabbing}
{\bf Procedure} {\tt S\ref{cons:urobust}.Encode}: \\
{\bf Input:} $K$, $m$, $h$ \\
Parse $m$ as $m_1^1 || m_2^1 || \cdots || m_l^1$\\
for \= $i = 1 \ldots l$ do \+ \\
	for \= $j = 1 \ldots n$ do \+ \\
		set $c_{i,j} = M(F_K(N,m_i),h)$  \\
		increment $N$\\
		set $h = h || c_{i,j}$ \-\-\\
{\bf Output:} $c_{1,1}|| c_{1,2}|| \ldots|| c_{l,n}$ 
\end{tabbing}
\end{minipage}\hspace{0.10in}\vline\hspace{0.10in}\begin{minipage}[t]{3.0in}
\begin{tabbing} 
{\bf Procedure} {\tt S\ref{cons:urobust}.Decode}: \\
{\bf Input:} key $K$, stegotext $c$, history $h$ \\
Parse $c$ as  $c^b_1 || c^b_2 || \ldots || c^b_{ln}$ \\
for \= $i = 1 \ldots l$ do \+ \\
	set $h_0 = h_1 = h$ \\
	for \= $j = 1 \ldots n$ do \+\\
		fo\=r $\sigma \in \{0,1\}$ do \+\\
		set $m_\sigma = M(F_K(N,\sigma), h_\sigma)$ \\
		set $h_\sigma = h_\sigma || m_\sigma$ \-\\
		increment $N$ \-\\
	if ($\forall j. (h_{0,j}, c_{i,j}) \in R'$) \\
	then $p_i = 0$;
	else $p_i = 1$\\	
	set $h = h_{p_i}$ \-\\
set $p = p_1 || p_2 || \cdots || p_l$.\\
{\bf Output:} $p$ 
\end{tabbing}
\end{minipage}
\end{center}
Suppose that instead of sharing a key to a pseudorandom function $F$,
Alice and Bob shared two secret blocks $b_0, b_1$ drawn independently from $\DD_h^b$.
Then Alice could send Bob the message bit $\sigma$ by sending block $b_\sigma$, and
Bob could recover $\sigma$ by checking to see if the block he received 
was related (by $R'$) to $b_0$ or $b_1$.  Since the adversary is $R$
bounded and $(\DD,R')$ is $\delta$-admissible, the probability of a
decoding error --- caused either by the adversary, or by accidental
draw of $b_0,b_1$ --- would be at most $\delta$.  Intuitively,
Construction~\ref{cons:urobust} simply extends this notion to multiple 
bits by replacing the $b_0,b_1$ by draws from $M(\cdot)$ with shared 
pseudorandom
inputs; and reduces the probability of decoding error to $\delta^n$ by encoding each
hiddentext bit $n$ times. 

\begin{lemma} \label{thm:urobust-ss}
$\insec{ss}{S\ref{cons:urobust},\DD}(t,q,l) \le \insec{prf}{F}(t + 
O(nl),nl).$
\end{lemma}
\TR{
\begin{proof}
Let $W$ be a passive warden which runs in time $t$, and makes at most $q$
queries of total length at most $l$.  We construct a PRF adversary $A$
which runs in time $t+\ell(l)$ and makes at most $\ell(l)$ queries to $F$, such that
$$\adv{prf}{F}(A) = \adv{ss}{S,\DD}(W)\ .$$  
The PRF adversary takes a function oracle $f$ and emulates the calls
$W$ makes to the encoder $\SE$ by using $f$ in place of $F_K(\cdot,\cdot)$.
More formally, we define the subroutine $SSE^f : \{0,1\}^\ast \times
\{0,1\}^\ast \rightarrow \{0,1\}^\ast$ as follows:
\begin{center}
\begin{minipage}[t]{3in}
\begin{tabbing}
{\bf Procedure} $SSE^f$: \\
{\bf Input:} A plaintext message $m$, history $h$ \\
Parse $m$ as $m_1^1 || m_2^1 || \cdots || m_l^1$\\
for \= $i = 1 \ldots l$ do \+ \\
	for \= $j = 1 \ldots n$ do \+ \\
		set $c_{i,j} = M(f(N,p_i),h)$  \\
		increment $N$\\
		set $h = h || c_{i,j}$ \-\-\\
{\bf Output:} $c_{1,1}|| c_{1,2}|| \ldots|| c_{l,n}$ 
\end{tabbing}
\end{minipage}
\end{center}
Then we define $A^f = W^{SSE^f,M}$; $A$'s advantage over $F$ is then:
\begin{eqnarray*}
\adv{prf}{F}(A) 
&=& \left| \Pr_{K \leftarrow U(k)}[A^{F_K(\cdot,\cdot)} = 1] - \Pr_{f \leftarrow U(L,l)}[A^f(\cdot,\cdot) = 1] \right| \\  
&=& \left| \Pr_{SE,K \leftarrow U(k)}[W^{\SE(K,\cdot,\cdot),M} = 1] - \Pr_{f \leftarrow U(L,l)}[A^f = 1] \right| \\  
&=& \left| \Pr_{SE,K \leftarrow U(k),r}[W_r^{\SE(K,\cdot,\cdot),M} = 1] - \Pr_{\DD,M,r}[W_r^{M,\DD} = 1] \right| \\
&=& \adv{ss}{S,\DD}(W)\ .
\end{eqnarray*}
Where the following cases for $f$ justify the substitutions:
\begin{itemize}
\item $f$ is chosen from $F_K(\cdot,\cdot)$.  Then the output
of $SSE^f$ is distributed identically to the encoding function of
Construction~\ref{cons:urobust}.  
That is, $\Pr_{K \leftarrow U(k)} [A^{F_K} = 1] = \Pr_{K \leftarrow U(k)}[W^{SE,M}=1]$.

\item $f$ is chosen uniformly.  Then by assumption on $M$, the
output of $SSE^f$ is distributed identically to a history dependent sample from
$\DD$; that is, $\Pr_{f \leftarrow U(L,l)}[A^f = 1] = \Pr_{\DD}[W^{\DD,M} = 1]$.
\end{itemize}

The claim follows by the definition of insecurity.
\end{proof}
}{\vspace{-6ex}}
\begin{lemma} \label{thm:urobust-robust}
$\fail{R}{S\ref{cons:urobust}}(t,q,l_1,l_2) \le \insec{prf}{F}(t +
O(nl),nl) + l_2\delta^n.$
\end{lemma}
\begin{proof}
Let $W$ be an active $R$-bounded $(t,q,l_1,l_2)$ warden.  We construct
a PRF adversary $A$ which runs in time $t + O(nl)$,
makes at most $nl$ PRF queries, and satisfies
$\adv{prf}{F}(A) \ge \success{R}{S}(W) - l_2\delta^n$. $A^f$ works by running $W$, using its function oracle $f$ in place of
$F_K(\cdot,\cdot)$ to emulate Construction~\ref{cons:urobust} in responding
to the queries of $W$.  Let $m,c'$ be the hiddentext and the stegotext
sequence returned by $W$, respectively.  Then $A^f$ returns 1 iff
$\SD(K,c',h) \neq m$.  Consider the following two cases for $f$:
\begin{itemize}
\item $f$ is chosen uniformly from all appropriate functions.  Then,
for each $i,j$, the stegotexts $c_{i,j} = M(f(N_i+j,p_i),h_{i,j})$ are distributed
independently according to $\DD_{h_{i,j}}^b$. Consider the sequence of
``alternative stegotexts'' $d_{i,j} = M(f(N_i+j,1-p_i),h_{i,j})$; each of these
is also distributed independently according to $\DD_{h_{i,j}}^b$; and
since $W$ is never given access to the $d_{i,j}$, the $c_{i,j}'$ are
independent of the $d_{i,j}$. Now $\SD$ will fail (causing $A^f$ to output 
1) only if the event $\forall j. (d_{i,j}, c_{i,j}') \in R'$ occurs
for some $i$. Because the $d_i$ are independent of the actions of $W$, and because
$(\DD,R')$ is $\delta$-admissible, each event $(d_{i,j}, c_{i,j}') \in 
R'$ happens independently with probability at most $\delta$. So for any fixed $i$, the
probability of failure is at most $\delta^n$.   The union bound then
gives $$\Pr_{f \leftarrow U(b,n)}[A^f = 1] \le l_2\delta^n.$$ 


\item $f$ is chosen uniformly from $F_K(\cdot,\cdot)$.  Then $A^F$
outputs 1 exactly when $W$ succeeds against S, by the definition of S:
$$\Pr_{K \leftarrow U(k), r \leftarrow \{0,1\}^\ast}[A_r^{F_K} = 1] =
\success{R}{S}(W)\ .$$

\end{itemize}
Taking the difference of these probabilities, we get: 
\begin{eqnarray*}
\adv{prf}{F}(A) &=& \Pr_{K \leftarrow U(k), r \leftarrow
\{0,1\}^\ast}[A^{F_K}_r = 1] - \Pr_{f \leftarrow U(b,n), r \leftarrow \{0,1\}^\ast}[A^f_r = 1]  \\
&\ge& \success{R}{S}(W) - l_2\delta^n \ .
\end{eqnarray*}
\end{proof}

\begin{thm}
If $F$ is $(t + O(nl),nl,\epsilon)$-pseudorandom then
Construction~\ref{cons:urobust} is
$(t,l_1,l_2,\epsilon,\epsilon+l_2 \delta^n)$-SR-CHA.
\end{thm}
\TR{\begin{proof} Conjunction of the previous two lemmas. \end{proof}
}{}

\subsection{Robust Steganography for text-like channels}

We provide a protocol which is steganographically robust against
$R$-bounded adversaries for a {\em particular} class of admissible
relations $R$ on \emph{particular} channels.  For some channel
distributions this class of relations may provide an accurate model of
the limitations of real wardens; in particular it seems reasonable to
suppose that a predominantly text-based channel might limit the power
of an active warden by such a relation.

A text based channel (such as email) might consist of ``documents''
built out of many bits with the same timestamp (= sending time).  Fix
a symbol alphabet $\Sigma = \left\{0,1\right\}^s$, and represent every
document $d$ in the support of $\DD$ by a string of symbols $d = d_0
d_1 \cdots d_l$ and a single timestamp.  The $n$-shingling of $d$,
denoted by $ss_n(d)$ is the set $\left\{ d_0d_1 \cdots d_{n-1},
d_1d_2 \cdots d_n, d_2d_3 \cdots d_{n+1}, \ldots,
d_{l-n}d_{l-n+1}\cdots d_l \right\}.$ Define the family of
relations $R_\delta^n$ for $0 \le \delta \le 1$ by
$$(x,y) \in R_\delta^n \Leftrightarrow \frac{|ss_n(x) \cap
ss_n(y)|}{|ss_n(x)\cup ss_n(y)|} \ge 1 - \delta\ .$$  

Let $F_K(\cdot,\cdot)$ denote a pseudorandom function family indexed
by $|K|$ bits which maps $n$-shingles to the set
$\left\{0,1\right\}^p$.  Let $E_K$ be a length-preserving, stateful
(rather than randomized), IND\$-CPA encryption scheme which works
by producing a pseudorandom stream $s$ and outputs $E_K(m) = s \oplus
m$, (such a scheme can be produced using a pseudorandom function in
(stateful) CTR mode, for example) and let $D$ be the corresponding
decryption function.  Let $Enc$ and $Dec$ be the encoding and decoding
algorithms for an error-correcting code which can correct up to a
$\delta + \xi$ fraction of symbol errors; and let $\ell(\cdot)$ be the
stretch function of this code.  We will assume $Enc$ and $Dec$ work in
linear time for simplicity.  Define the function $\mbox{max}_f(d)$ as
the shingle in $d$ which maximizes $f$, that is $$\mbox{max}_f(d) =
\operatorname{argmax}_{s \in ss_n(d)} \left\{ f(s) \right\}\ .$$ Let
$g : \left\{0,1\right\}^\ast \rightarrow \left\{0,1\right\}$ be
unbiased for the distribution on shingles induced by
$\mbox{max}_{F_K}(\DD)$.  Let Alice and Bob share secret keys $K_f,
K_e$. The following procedures allow Alice and Bob to robustly encode
and decode a message.

\begin{cons} \label{cons:robust} (Robust Steganographic Protocol) \end{cons}

\begin{center}
\begin{minipage}[t]{3in}
\begin{tabbing}
{\bf Procedure} {\tt S\ref{cons:robust}.Encode}: \\
{\bf Input:} $m$, $h$, keys $K_f,K_e$ \\
Let $p = E_{K_e}(Enc(m))$\\
Parse $p$ as $p_1^1 || p_2^1 || \cdots || p_l^1$\\
for \= $i = 1 \ldots l$ do \+ \\
set $c_i = RS^{M(h),g \circ \max_{F_{K_f}}}(p_i)$ \\
%re\=peat: \+\\ 
%	$c_i \leftarrow M(h)$  \\
%	set $s_i = \max_{F(K_f,\cdot)}(c_i)$ \- \\
%until $g(s_i) = p_i$ \\
set $h = h || c_i$ \-\\
{\bf Output:} $c_1|| c_2|| \ldots|| c_l$ 
\end{tabbing}
\end{minipage}\hspace{0.10in}\vline\hspace{0.10in}\begin{minipage}[t]{3in}
\begin{tabbing} 
{\bf Procedure} {\tt S\ref{cons:robust}.Decode}: \\
{\bf Input:} stegotext $c$, keys $K_f, K_e$ \\
Parse $c$ as  $c^b_1 || c^b_2 || \ldots || c^b_l$ \\
for \= $i = 1 \ldots l$ do \+ \\
set $s_i = \max_{F_{K_f}(\cdot)}(c_i)$ \\
set $p_i = g(s_i)$ \- \\
set $p = p_1 || p_2 || \cdots || p_l$.\\
{\bf Output:} $Dec(D_{K_e}(p))$ 
\end{tabbing}
\end{minipage}
\end{center}

Note that it is important that encryption and bit errors commute here
which holds for only some encryption techniques. 

\noindent In the following, Let $\ell_q$ be the maximum size of $q$
encoded strings with total length $l_1$ plus $\ell(l_2)$.

\begin{lemma} \label{lemma:secret}
$\insec{ss}{S\ref{cons:robust}}(t,q,l) \le
\insec{cpa}{E}(t + O(k \ell_q), q, \ell_q).$
\end{lemma}

\TR{\begin{proof}
Given a passive warden $W$ which runs in time $t$ and makes at most
$q$ queries which encode to a total of $l$ bits, we construct a CPA adversary $A$ such that
$$\adv{ss}{S,\DD}(W) = \adv{cpa}{E}(A)\ ,$$
where $A$ runs in time at most $t + kl$, 
and submits at most $q$ queries totaling $l$ bits of plaintext to
the encryption oracle.  

$A$ uses the simulated encryption subroutine $SSE^E(K_f,m,h)$ defined by:
\begin{center}
\begin{minipage}[t]{3in}
\begin{tabbing}
{\bf Procedure} $SSE^E$: \\
{\bf Input:} key K, plaintext message $m$, history $h$ \\
Let $p = E(Enc(m))$\\
Parse $p$ as $p_1^1 || p_2^1 || \cdots || p_l^1$\\
for \= $i = 1 \ldots l$ do \+ \\
set $c_i = RS^{M(h), g \circ \max_{F_{K_f}}(\cdot)}(p_i)\ .$\\
set $h = h || c_i$ \-\\
{\bf Output:} $c_1|| c_2|| \ldots|| c_l$ 
\end{tabbing}
\end{minipage}
\end{center}
A then simulates a chosen-hiddentext attack by choosing a random key
$K_f$ and running $W^{SSE^E(K_f,\cdot,\cdot)}$. Consider the two cases for $E$:

\begin{enumerate}
\item $E = E_K$ for a uniformly chosen $K$. 
Then the stegotexts returned by SSE are distributed identically to documents constructed
from $S$.  In this case, $$\Pr_{K_e \leftarrow U(k_e), s, r \leftarrow
\{0,1\}^\ast }[A^{E_{K_e,s}}_r = 1] =
\Pr_{K \leftarrow U(k_e + k_f), M, SE, r}[W^{M, \SE(K,\cdot,\cdot)}_r = 1]\ .$$

\item The encryption oracle returns uniformly chosen strings 
In this case, the stegotexts returned by $SSE^E$ are sampled identically to the
distribution $\DD_h$. This follows by the unbiasedness of $g \circ
\max_{F_{K_f}}$ and the fact that the parsed substrings $p_i$ are
uniformly distributed on $\left\{0,1\right\}$.  So $$\Pr_{g,r}[A^{g(\cdot)}_r 
= 1] = \Pr_{M, r,O}[W_r^{M,O(\cdot,\cdot)} = 1]\ .$$ 

\end{enumerate}

Then the CPA advantage of $A$ is:
\begin{eqnarray*}
\adv{cpa}{E}(A) &=& 
\left| 
\Pr_{K_e,s,r}[A^{E_{K_e,s}}_r = 1] - \Pr_{g,r}[A^g = 1]
\right| \\
&=& 
\left| 
\Pr_{K \leftarrow U(k_e + k_f), M, SE, r}[W^{M, \SE(K,\cdot,\cdot)}_r = 1] -
\Pr_{M, r,O}[W_r^{M,O(\cdot,\cdot)} = 1]
\right|\ \\
&=& \adv{ss}{S,\DD}(W)\ .\\
\end{eqnarray*}

This gives the required bound.

\end{proof}
}{}

\begin{lemma} \label{lemma:robust}
$\fail{R_\delta^n}{S\ref{cons:robust}}(t,q,l_1, l_2) \le
2 e^{-\xi^2 \ell(l_2)/2} + \insec{prf}{F}(t+O(k \ell_q), k\ell_q).$
\end{lemma}

\TR{
\begin{proof}
Given an $R_\delta^n$-bounded active warden $W$ which runs in time $t$
against a message of length $l_2$, we will produce an adversary $A$
which runs in time $t + k\ell_qb$, makes at most $k\ell_qb$ queries to $F$
and satisfies $$\adv{prf}{F}(A) \ge \success{R_\delta^n}{S}(W)
- 2 e^{-\xi^2\ell(l_2)/2}\ .$$ 

$A^f$ uses two subroutines $SSE^f, SSD^f$ defined as follows:
\begin{center}
\begin{minipage}[t]{3in}
\begin{tabbing}
{\bf Procedure} $SSE^f$: \\
{\bf Input:} Key $K_e$, message $m$, history $h$ \\
Let $p = E_{K_e}(R,Enc(m))$\\
Parse $p$ as $p_1^1 || p_2^1 || \cdots || p_l^1$\\
for \= $i = 1 \ldots l$ do \+ \\
set $c_i = RS^{M(h),g \circ \max_{f}(\cdot)}(p_i,k)$.\\
set $h = h || c_i$ \-\\
{\bf Output:} $c_1|| c_2|| \ldots|| c_l$ 
\end{tabbing}
\end{minipage}\hspace{0.25in}\vline\hspace{0.25in}\begin{minipage}[t]{3in}
\begin{tabbing} 
{\bf Procedure} $SSD^f$: \\
{\bf Input:} Key $K_e$, Covertext $c$ \\
Parse $c$ as  $c^b_1 || c^b_2 || \ldots || c^b_l$ \\
for \= $i = 1 \ldots l$ do \+ \\
set $s_i = \max_{f}(c_i)$ \\
set $p_i = g(s_i)$ \- \\
set $p = p_1 || p_2 || \cdots || p_l$.\\
{\bf Output:} $Dec(D_{K_e}(p))$ 
\end{tabbing}
\end{minipage}
\end{center}
$A^f$ then uses these subroutines to simulate $W$:
\begin{enumerate}
\item $A$ picks a key $K_e \leftarrow U(k_e)$.
\item $A$ computes $(m_W, h_W) = W^{SSE^f(K_e, \cdot,\cdot)}$.
\item $A$ computes $c = SSE^f(K_e, m_W, h_W)$.
\item $A$ returns 1 if $SSD^f(K_e, W(c)) \ne m_W$.
\end{enumerate}

Consider the two separate cases for $A$'s function oracle:
\begin{itemize}
\item If $f$ is a random function, then the probability that $W$
alters the shingle $\max_f(c_i)$ for any single stegotext $c_i$ is at
most $\delta$, since $W$ alters at most a $\delta$ fraction of the
shingles from each $c_i$, and $\max_f(c_i)$ is chosen uniformly from
these shingles.  $A$ can return 1 only when this event
happens on more than $(\xi + \delta)\ell(l_2)$ covertexts (otherwise $Dec$
can correct the symbol errors).  Define the indicator random
variables $X_i$ to be 1 if $W$ alters the shingle $\max_f(c_i)$ and 0
otherwise.  By considering the martingale sequence given by $Y_0 =
E[\sum X_i]$, $Y_j = E[\sum X_i | X_1,\ldots,X_j]$ we can use
Azuma's inequality \cite{MR95} to obtain the bound 
$$\Pr\left[ \sum X_i \ge (\delta + \xi)\ell(l_2) \right] < 2
e^{-\xi^2\ell(l_2)/2}\, $$
Which by definition of the $X_i$ gives us
$$\Pr_{f \leftarrow U(n,1), r \leftarrow \{0,1\}^\ast}[A^f_r = 1] \le 2e^{-\xi^2\ell(l_2)/2}\ .$$

\item If $F$ is sampled from $F_K(\cdot)$ then $A^F$ returns 1
exactly when $W$ succeeds. Thus $$\Pr_{K \leftarrow U(k), r}[A^{F_K}_r = 1] = \success{R_\delta^n}{S}(W)\ .$$
\end{itemize}
Combining these cases, we have that
\begin{eqnarray*}
\adv{prf}{F}(A) &=&  \Pr_{K,r}[A^{F_K}_r = 1] - \Pr_{f,r}[A^f_r = 1] \\
		&\ge& \success{R_\delta^n}{S}(W) - 2e^{-\xi^2\ell(l_2)/2}
\end{eqnarray*}
Which satisfies the desired bound.  As to the time and query
parameters, note that every call to $RS^{M(h),g \circ
\max_{f}(\cdot)}(\cdot,k)$ makes at most $b$ calls to $f$ per call to
$\max_f$, and makes at most $k$ calls to $\max_f$; since $A^f$ makes
at most $\ell_q$ calls to $RS$, the total number of calls to $f$ is at most
$k\ell_qb$ (and is an expected $O(\ell_qb)$); and the running time is at most
the running time of $W$ plus the time consumed in $RS$.
\end{proof}
}{}

\begin{thm}
If $F$ is $(t+O(k \ell_q), k \ell_q, \epsilon)$-pseudorandom and $E$
is $(t+\ell_q, q, \ell_q, \mu)$ - IND\$-CPA, then
Construction~\ref{cons:robust} is
$(t,l_1,l_2,\epsilon+\mu,2 e^{-\xi^2\ell(l_2)/2}+\epsilon)$ - SR-CHA
against $R_\delta^n$-bounded adversaries.
\end{thm}
\TR{\begin{proof}
Follows from lemmas~\ref{lemma:secret} and~\ref{lemma:robust}.
\end{proof}
}{}
\TR{Note that the error term resulting from the tail bound in this
construction can be made arbitrarily small by setting a minimum 
message size in the encoding routine.}{\vspace{-4ex}}

\section{Discussion}
\label{sec-discussion}
\TR{
\subsection{Rate and Efficiency}

The steganographic literature is often concerned with the {\em rate} of a
stegosystem.  We can define the rate of a stegosystem $S$ as the number of
bits of plaintext divided by the number of bits in the covertexts.  
Ignoring the probability of failure and the use of error correcting codes,
the expected rate of our constructions is $1/b$.
}{\vspace{-1.5ex}}
\subsection{Alternative security conditions}
There are several conceivable alternatives to our security
conditions; we will briefly examine these alternatives and justify our 
choices.

{\em Find-Then-Guess:} This is the standard model in which an attacker
submits two plaintexts $p_0$ and $p_1$, receives $\SE(p_b)$, and
attempts to guess $b$. Security in our attack model implies
find-then-guess security; moreover the essence of steganographic
secrecy is not merely the inability to distinguish between messages
(as in the find-then-guess model) but the inability to detect a message.

{\em Fixed History:} In this model the adversary may not submit
alternate histories to the encryption model.  Security under a
chosen-history attacks implies security against a fixed-history
attacks.  This notion may be of interest however, especially because in
many situations a chosen-history attack may not be physically
realizable.  Our attacks can be considered chosen-history attacks.

{\em Integrity of Hiddentexts}.  Intuitively, Integrity of Hiddentexts
requires that an active warden is unable to create a sequence of 
covertexts which decodes to a valid, new hiddentext. Suppose we amend the
description of a stego system to allow the decoding algorithm to
output the ``fail'' symbol $\perp$. Then suppose we give the adversary
oracle access to $\SE$ and allow the adversary to make at most $q$
queries $p_0,\ldots,p_q$ to $\SE(K,\cdot,\cdot)$ totaling $l$ bits.
The adversary then produces a sequence of covertexts $c =
c_1||\ldots||c_m$.  Denote the advantage of $A$ against $S$ by
$$\adv{int}{S, \DD}(A) = \Pr\left[\SD(K,\vec{c},h) \ne \perp \wedge
\forall i . \SD(K,\vec{c},h) \ne p_i\right]\ ,$$ and denote the
integrity failure of a stegosystem by
$$\fail{int}{S,\DD}(t,q,l) = \max_{A \in \mathcal{A}(t,q,l)} \left\{ \adv{int}{S, \DD}(A) \right\}\ .$$
A stegosystem has $(t,q,l,\epsilon)$ integrity of
hiddentexts if $\fail{\mbox{int}}{S, \DD}(t,q,l) \le \epsilon$.  

Note that in practice this notion by itself is too weak because it
allows the possibility for the warden to disrupt the communication
between Alice and Bob.  Finally, we note that if the symmetric encryption scheme $E$ is
INT-CTXT secure as defined by Bellare and Namprempre \cite{BN01}, then
construction \ref{cons:hash} also provides integrity of hiddentexts.

\TR{}{\vspace{-1ex}}
\subsection{Complexity theoretic ramifications}
\TR{}{\vspace{-1ex}}
Construction~\ref{cons:nohash} gives a stegosystem
which is steganographically secret for any channel distribution $\DD$
which has minimum entropy greater than $1$, assuming the existence of
a pseudorandom function family.  Goldreich {\em et al} \cite{GGM86}
show how to construct a pseudorandom function from a pseudorandom
generator, which in turn can be constructed from any one-way function,
as demonstrated by Hastad {\em et al} \cite{HILL99}.  Thus in an
asymptotic sense, our constructions show that one-way functions are
sufficient for steganography.  Conversely, it is easy to see that a
stegosystem which is steganographically secret for some $\DD$ is a
secure weak private key encryption protocol in the sense of
Impagliazzo and Luby \cite{IL89}; and they prove that the existence of
such a protocol implies the existence of a one-way function.  Thus the
existence of secure steganography is equivalent to the existence of
one-way functions.

\TR{}{\vspace{-1.5ex}}
\subsubsection*{Acknowledgments}

We are greatful to Manuel Blum for his suggestions and his unconditional
encouragment. We also thank Steven Rudich and the anonymous CRYPTO
reviewers for helpful discussions and comments. This work was partially 
supported by the National Science Foundation (NSF)
grants CCR-0122581 and CCR-0085982 (The Aladdin Center). Nicholas Hopper 
is also partially supported by an NSF graduate research fellowship. 

\TR{}{\vspace{-1.5ex}}
\begin{thebibliography}{1}
\TR{}{\vspace{-1.5ex}}
\bibitem{AP98} Ross J. Anderson and Fabien A. P. Petitcolas. 
\newblock {\em On The Limits of Steganography}. 
\newblock IEEE Journal of Selected Areas in Communications, 16(4). May
1998.

\bibitem{BN01} Mihir Bellare and Chanathip Namprempre.
\newblock {\em Authenticated Encryption: Relations among notions and
analysis of the generic composition paradigm}.
\newblock In: {\em Advances in Cryptology -- Asiacrypt '00}. December
2000.


\bibitem{C98} 
\newblock C. Cachin.
\newblock {\em An Information-Theoretic Model for Steganography}.  
\newblock In: {\em Information Hiding -- Second International
Workshop, Preproceedings}. April 1998. 

\TR{
\bibitem{C96} \newblock S. Craver. \newblock {\em On Public-Key
Steganography in the Presence of an Active Warden}. \newblock In:
{\em Information Hiding -- Second Internaitonal Workshop, Preproceedings}.
April 1998.
}{}

\bibitem{GGM86} Oded Goldreich, Shafi Goldwasser and Silvio Micali.
\newblock {\em How to Construct Random Functions}.
\newblock Journal of the ACM, 33(4):792 -- 807, 1986.

\bibitem{HILL99} Johan Hastad, Russell Impagliazzo, Leonid A. Levin, and
Michael Luby.  \newblock {\em A pseudorandom generator from any one-way
function}.  \newblock SIAM Journal on Computing, 28(4):1364--1396, 1999. 

\TR{}{
\bibitem{HLvA02} Nicholas J. Hopper, John Langford, and Luis von Ahn. 
\newblock {\em Provably Secure Steganography}.  CMU Tech Report CMU-CS-TR-02-149, 2002.
}

\bibitem{IL89} Russell Impagliazzo and Michael Luby.
\newblock {\em One-way Functions are Essential for Complexity Based
Cryptography}.
\newblock In: 30th FOCS, November 1989.

\TR{
\bibitem{J95} \newblock G. Jagpal.
\newblock {\em Steganography in Digital Images}
\newblock Thesis, Cambridge University Computer Laboratory, May 1995. 
}{}

\bibitem{K67} D. Kahn.
\newblock {\em The Code Breakers}.
\newblock Macmillan 1967.

\bibitem{KP99} Stefan Katzenbeisser and Fabien A. P. Petitcolas. 
\newblock {\em Information hiding techniques for steganography and
digital watermarking}. 
\newblock Artech House Books, 1999.

\TR{
\bibitem{LR87} Michael Luby and Charles Rackoff.
\newblock {\em How to construct pseudorandom permutations from
pseudorandom functions}.
\newblock SIAM Journal on Computing, 17(2):373 -- 386, 1988. 

\bibitem{MT94}
\newblock K. Matsui and K. Tanaka.
\newblock {\em Video-steganography.}
\newblock In: {\em IMA Intellectual Property Project Proceedings}, volume
1,
pages 187--206, 1994. 
}{}

\bibitem{M00} \newblock T. Mittelholzer.  \newblock {\em An
Information-Theoretic Approach to Steganography and Watermarking}
\newblock In: {\em Information Hiding -- Third International Workshop}.
2000.

\TR{
\bibitem{MR95} Rajeev Motwani and Prabhakar Raghavan.
\newblock {\em Randomized Algorithms}.
\newblock Cambridge University Press, 1995. 
}{}

\bibitem{OME98}
\newblock J. A. O'Sullivan, P. Moulin, and J. M. Ettinger  
\newblock {\em Information theoretic analysis of Steganography}.  
\newblock In: {\em Proceedings ISIT `98}. 1998.


\bibitem{RBBK01} Phillip Rogaway, Mihir Bellare, John Black and Ted
Krovetz.
\newblock {\em OCB: A Block-Cipher Mode of Operation for Efficient
Authenticated Encryption}.
\newblock In: {\em Proceedings of the Eight ACM Conference on Computer and
Communications Security (CCS-8)}. November 2001.

\bibitem{S83} G.J. Simmons. 
\newblock {\em The Prisoner's Problem and the Subliminal Channel}. 
\newblock In: {\em Proceedings of CRYPTO '83}. 1984.

\TR{
\bibitem{WW98} \newblock A. Westfeld, G. Wolf.  \newblock {\em
Steganography in a Video Conferencing System}.  \newblock In:
{\em Information
Hiding -- Second International Workshop, Preproceedings.}  April 1998. 
}{}

\bibitem{ZF98} J Zollner, H.Federrath, H.Klimant, A.Pftizmann, R. Piotraschke, A.Westfield, G.Wicke, G.Wolf. 
\newblock {\em Modeling the security of steganographic systems}. 
\newblock In: 
{\em Information
Hiding -- Second International Workshop, Preproceedings.}  April 1998. 

 
\end{thebibliography}

\end{document}





