\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}