\documentclass{llncs}
\usepackage{amsmath}
%\usepackage{amsthm}
\usepackage{amsfonts}
%\usepackage[T1]{fontenc}
\usepackage{fullpage}

\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{\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}    
\newtheorem{thm}{Theorem}
\newtheorem{cor}{Corollary}
%\numberwithin{equation}{section} %% Comment out for sequentially-numbered
%\numberwithin{figure}{section} %% Comment out for sequentially-numbered
%\theoremstyle{definition}
\spnewtheorem{defn}{Definition}{\bfseries}{}
%\newtheorem{lemma}[thm]{Lemma}
\newtheorem{cons}{Construction}
\spnewtheorem*{defn*}{Definition}{\bfseries}{}
\newcommand{\comment}[1]{}

\makeatother

\begin{document}
\title{Companion to ``Provably Secure Steganography''}
\author{Nicholas J. Hopper \and John Langford \and Luis von Ahn}
\institute{Carnegie Mellon University\\
{\tt \{hopper,jcl,biglou\}@cs.cmu.edu}}
\date{}
\maketitle

\renewcommand{\baselinestretch}{0.97}

\begin{abstract}
We point out and correct a flaw in our paper ``Provably Secure 
Steganography'', which appeared in the proceedings of CRYPTO 
2002. The claims of the paper remain correct, but small changes need to be 
made in one of our protocols. 
\end{abstract}

\section{Introduction}

Lea Kissner, Tal Malkin and Omer Reingold have pointed out a small flaw 
in our paper ``Provably Secure Steganography''. The flaw 
has to do with Construction 1 in Section 3.1. In this construction, $RS$ 
samples the channel oracle $|K|$ times. As Kissner, Malkin and Reingold 
point out, this construction, as stated, is insecure. Luckily, the 
construction remains secure if $RS$ samples from the oracle only twice. 
Hence, the construction should be changed to the following:

\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, 2)$ \\
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}

\noindent The following section (in conjunction with our paper) should 
prove the 
correctness of this construction.

\section{Correctness}

\subsection*{Notation}

Assume the channel has symbols $\{S_1,...,S_k\}$ with probabilities 
$p_1,...,p_k$. 
Assume $f$ is a random function from $\{S_1,...,S_k\}$ to $\{0,1\}$. 
Consider the following experiment: 

\begin{quote}
Draw from the channel to get a symbol $S$. If $f(S)=0$ output $S$. 
Otherwise draw again from the channel and output the result.
\end{quote}

\noindent Denote the outcome of this experiment by $S_E$. 
\\
\\
\noindent
Let $D$ be the event that after drawing twice from the channel you 
get a different symbol (a non-collision). 
Let $\overline{D}$ denote the event that after drawing twice from the 
channel 
you get the same symbol. 

\subsection*{Lemmas}

We need to show that drawing from the channel with replacement twice 
doesn't change the distribution. In other words:

\begin{lemma} 
\[\Pr_{f,\DD}[S_E=S_i]=p_i\]
\end{lemma}

\begin{proof} 


\begin{eqnarray*}
\Pr_{f,\DD}[S_E=S_i] & = & p_i/2+
\frac{p_i}{4}\sum_{j\neq i}p_j+
\frac{p_i}{4}\sum_{j\neq i}p_j+
p_i^2/2 \\
& = & p_i/2+p_i(1-p_i)/2+p_i^2/2\\
& = &p_i
\end{eqnarray*}

The first line is true because the probability of getting symbol $S_i$ is 
the sum of the probabilities of the following disjoint events:

\begin{itemize}
\item The first draw from the channel results in $S_i$ and $f(S_i)=0$.

\item The first draw from the channel is $S_j$ for $i\neq j$ and 
$f(S_j)=1$ and the second draw from the channel is $S_i$ and $f(S_i)=0$. 

\item The first draw from the channel is $S_j$ for $i\neq j$ and 
$f(S_j)=1$ and the second draw from the channel is $S_i$ and $f(S_i)=1$. 

\item The first draw from the channel is $S_i$ and $f(S_i)=1$ and the 
second draw from the channel is $S_i$. 

\end{itemize}

\end{proof}

\noindent Next we need to show that drawing twice from the channel 
results 
in a symbol that maps to the correct bit with a probability bounded away 
from $1/2$:

\begin{lemma} 
\[\Pr_{f,\DD}[f(S_E)=0] > 5/8\]
\end{lemma}

\begin{proof}

First, note that:

\[\Pr_{f,\DD}[f(S_E)=0]= \frac{1}{2}+\frac{1}{4}\Pr_{f,\DD}[D]\]

\noindent The right side is the sum of the probabilities of the following 
disjoint 
events:

\begin{itemize}
\item The first draw results in a symbol that maps to zero.
\item The first draw results in a symbol that maps to 1 and the second 
draw results in a {\it different} symbol that maps to 0.
\end{itemize}


\noindent Let $S_i$ be a symbol with highest probability 
($p_i \geq p_j$ for all $j$), then 
\[\Pr_{f,\DD}[\overline{D}]=p_1^2+...+p_k^2 \leq p_i(p_1+...+p_k)\]
So $\Pr_{f,\DD}[D]\geq (1-p_i)$, and we have that

\begin{eqnarray*}
\Pr_{f,\DD}[f(S_E)=0] & \geq & \frac{1}{2}+\frac{1}{4}(1-p_i)\\
& > & \frac{1}{2} + \frac{1}{8}
\end{eqnarray*}
(since we are assuming that $H_{\infty}(\DD)>1$). 


\end{proof}


\subsubsection*{Acknowledgments}

We are greatful to Lea Kissner, Tal Malkin and Omer Reingold for
pointing out the flaw in our paper.


\begin{thebibliography}{1}

\bibitem{HLvA02} Nicholas J. Hopper, John Langford and Luis von Ahn.
Provably Secure Steganography. In {\it Proceedings of CRYPTO
2002}.

\end{thebibliography}

\end{document}


