\documentstyle[fancybox,portrait]{seminar}

\landscapeonly \special{landscape}

\input epsf

%----------------------------------------------------
\newpagestyle{11}%
 {~~ \hspace{\fill}\rightmark \hspace{\fill}\thepage}
 {\hspace{3\semcm} PET'03 \hspace{\fill}}%

\pagestyle{11}

\markright{Breaking and Mending Resilient Mix-nets}

\newcommand{\heading}[1]{%
  \begin{center}
    \large\bf \shadowbox{#1}
  \end{center}
  \vspace{1ex minus 1ex}}
%----------------------------------------------------

%\slidewidth  230mm


\def\bi{\begin{itemize}}
\def\ei{\end{itemize}}
\def\be{\begin{enumerate}}
\def\ee{\end{enumerate}}


\begin{document}

\renewcommand{\paperwidth}{297mm}
\renewcommand{\paperheight}{200mm}

\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}

\slideframewidth=1pt


\begin{slide}

\begin{center}
{\bf Breaking and Mending Resilient Mix-nets}
\end{center}
\vspace{1cm}
\begin{center}
Lan Nguyen and Rei Safavi-Naini\\
$\hspace{.8in}$\\
School of IT and CS \\
University of Wollongong\\
Wollongong 2522\\
Australia \\
{\sl email: [ldn01,rei]@uow.edu.au}
\end{center}

\newpage
\begin{center}
{\bf Outline}
\end{center}

\bi
 \item Mix-net description and its requirements
 \item Cryptographic tools for discussed mix-nets
 \item Furukawa-Sako mix-net\cite{Furukawa01} and Millimix\cite{Jakobsson99-2}
 \item Attacking Furukawa-Sako scheme and Millimix
 \item Countermeasures and their efficiency and
 security analysis.
\ei

\newpage
\heading{Mix-net}

Mix-net protects privacy of messages in network communication.  A
mix-net consists of a set of mix servers, each receiving as input
a list of ciphertexts and outputting either a permuted list of the
re-encrypted ciphertexts, or a permuted list of the corresponding
plaintexts.\\
Mix-net participants:
\bi
 \item \emph{Users} send messages to mix-net.
 \item \emph{Mix servers} perform mixing of the input messages
 and produce an output, which is used as input to other
 mix-servers.
 \newpage
 \item \emph{Verifier} verifies correctness of the mix-net
 operation.
 \item \emph{Bulletin board} is a shared memory where all participants have read
 access to and can append messages after being authenticated. It
 simulates an authenticated broadcast channel.
 \item \emph{Adversary} tries to compromise
 resiliency of the mix-net. We assume \emph{static adversary}.
\ei

\newpage
\heading{Mix-net Requirements}

A mix-net is \emph{resilient} if it satisfies \emph{privacy},
\emph{robustness} and \emph{verifiability}.
\begin{itemize}
  \item \emph{privacy:} the adversary cannot
  output a pair of input and the corresponding output with probability non-negligibly greater than random guess.
  \item \emph{verifiability:} the verification can detect and reveal the identities of the
  cheating servers with overwhelming probability. If only publicly available information is used, the mix-net is called
  \emph{universally verifiable}.
  \item \emph{robustness:} ensures that the probability of
  producing incorrect output is negligibly less than 1.
\end{itemize}

\newpage
\heading{Cryptographic tools}

\textbf{El Gamal encryption} $p$ and $q$ are primes, $p=2kq+1$,
$g$ is a generator of subgroup $G_q$ of order q in $Z_p^{*}$.
Private key is $x \in Z_q$, public key is $(y,g)$ where
$y=g^x$.\\
A ciphertext of message $m \in G_q$ is $(\alpha,\beta)$ where
$\alpha=my^{s}$, $\beta=g^{s}$, $s \in_R Z_q$. The plaintext is
computed as $m:=\alpha/\beta^{x}$. A re-encryption of ciphertext
$(\alpha,\beta)$ is $(\alpha \times y^{r},\beta \times g^{r})$,
where $r \in_R Z_q$.\\
\textbf{Schnorr identification} ${\cal P}$ shows knowledge of
private key $x$ to ${\cal V}$
\begin{enumerate}
  \item ${\cal P} \longrightarrow {\cal V}$: a commitment
  $w=g^{e}$, where $e \in_R Z_q$
  \item ${\cal P} \longleftarrow {\cal V}$: a challenge $c \in_R Z_q$
  \item ${\cal P} \longrightarrow {\cal V}$: a response
  $s=e+cx$ mod $q$
\end{enumerate}
${\cal V}$ then verifies that $g^{s}=wy^{c}$.\\
\textbf{Disjunctive Schnorr identification} ${\cal P}$ shows he
knows one of private keys $x_1$ or $x_2$ to ${\cal V}$. Assume
${\cal P}$ possesses $x_1$.
\begin{enumerate}
  \item ${\cal P} \longrightarrow {\cal V}$: two commitments
  $w_1=g_1^{e_1}$, $w_2=g_2^{s_2}y_2^{-c_2}$, where $e_1,e_2,c_2,s_2 \in_R Z_q$
  \item ${\cal P} \longleftarrow {\cal V}$: a challenge $c \in_R Z_q$
  \item ${\cal P} \longrightarrow {\cal V}$: responses
  $s_1=e_1+c_1x_1$ mod $q$, $s_2$, $c_1=c \oplus c_2$, $c_2$
\end{enumerate}
${\cal V}$ then checks if $g_i^{s_i}=w_iy_i^{c_i}$ for $i \in
\{1,2\}$.\\
\textbf{Pairwise permutation network} A \emph{pairwise permutation
network} is a permutation that is constructed from switching gates
and requires $n\log_{2}n-n+1$ switching gates. A \emph{switching
gate} is a permutation for two input items.
\newpage
\textbf{Permutation Matrix} A matrix $(A_{ij})_{n\times n}$ is a
permutation matrix $\Leftrightarrow$ $\exists$ $\phi$ so that
$\forall i, j \in \{1,...,n\}$
\begin{eqnarray*}
A_{ij} &=& \left\{ \begin{array}{ll}
                    1 \mbox{ mod } q& \mbox{if $\phi(i)=j$}\\
                    0 \mbox{ mod } q& \mbox{otherwise}
\end{array}
\right.
\end{eqnarray*}
\underline{Theorem 1} $(A_{ij})_{n\times n}$ is a permutation
matrix $\Leftrightarrow$ $\forall i, j, k \in \{1,...,n\}$
\begin{eqnarray}
\label{eqn:eqn1} \sum_{h=1}^n A_{hi}A_{hj} &=& \left\{
\begin{array}{ll}
                    1 \mbox{ mod } q& \mbox{if $i=j$}\\
                    0 \mbox{ mod } q& \mbox{otherwise}
\end{array}
\right. \\
\label{eqn:eqn2} \sum_{h=1}^n A_{hi}A_{hj}A_{hk} &=& \left\{
\begin{array}{ll}
                    1 \mbox{ mod } q& \mbox{if $i=j=k$}\\
                    0 \mbox{ mod } q& \mbox{otherwise}
\end{array}
\right.
\end{eqnarray}

\newpage
\heading{Furukawa-Sako01 Mix-net}

Input to a mix-server is El Gamal ciphertexts
$\{(g_i,m_i)|i=1,...,n\}$ encrypted by $(y, g)$. Output is
$\{(g_i',m_i')|i=1,...,n\}$\\
The mix-server proves knowledge of a permutation matrix
$(A_{ij})_{n\times n}$ and $\{r_i|i=1,...,n\}$
\begin{eqnarray}
g_i' &=& g^{r_i}\prod_{j=1}^n g_j^{A_{ji}} \label{eqn:eqn3}\\
m_i' &=& y^{r_i}\prod_{j=1}^n m_j^{A_{ji}} \label{eqn:eqn4}
\end{eqnarray}
\newpage
Based on Theorem 1, this can be done by proving:
\begin{itemize}
  \item $\{g_i'\}$ can be
  expressed as (\ref{eqn:eqn3}) using a matrix satisfying (\ref{eqn:eqn1}).
  \item $\{g_i'\}$ can be
  expressed as (\ref{eqn:eqn3}) using a matrix satisfying (\ref{eqn:eqn2}).
  \item The matrix and $\{r_i\}$ in these statements are the
  same.
  \item For each $(g_i',m_i')$, the same $r_i$ and
  $\{A_{ij}\}$ is used.
\end{itemize}

\newpage
\heading{Furukawa-Sako01 Verification Protocol}

Suppose $\{\tilde{g}, \tilde{g_1}, ..., \tilde{g_n}\}$ so that
under discrete logarithm assumption, infeasible to obtain
$\{a_i\}$ and $a$ satisfying $\tilde{g}^a \prod_{i=1}^n
\tilde{g_i}^{a_i}=1$.
\begin{enumerate}
  \item ${\cal P}$ generates: $\delta, \rho, \tau,
  \alpha, \alpha_i, \lambda, \lambda_i \in_R Z_q, i=1,...,n$
  \item ${\cal P}$ computes:
    \[t=g^{\tau},v=g^{\rho},w=g^{\delta},u=g^{\lambda},u_i=g^{\lambda_i}, i=1,...,n \]
    \begin{eqnarray}
    \label{eqn:eqn5}
    \tilde{g_i}' & = & \tilde{g}^{r_i}\prod_{j=1}^n \tilde{g_j}^{A_{ji}}, i=1,...,n \\
    \label{eqn:eqn6}
    \tilde{g}'   & = & \tilde{g}^{\alpha}\prod_{j=1}^n \tilde{g_j}^{\alpha_j} \\
    g'           & = & g^{\alpha}\prod_{j=1}^n g_j^{\alpha_j} \label{e1}\\
    m'           & = & y^{\alpha}\prod_{j=1}^n m_j^{\alpha_j} \label{e2}\\
    \dot{t_i}          & = & g^{\sum_{j=1}^n 3\alpha_jA_{ji}+\tau\lambda_i}, i=1,...,n \label{e3} \\
    \dot{v_i}          & = & g^{\sum_{j=1}^n 3\alpha_j^2 A_{ji}+\rho r_i}, i=1,...,n \label{e4} \\
    \dot{v}            & = & g^{\sum_{j=1}^n \alpha_j^3+\tau\lambda+\rho\alpha} \label{e5} \\
    \dot{w_i}          & = & g^{\sum_{j=1}^n 2\alpha_jA_{ji}+\delta r_i}, i=1,...,n \label{e6} \\
    \dot{w}            & = & g^{\sum_{j=1}^n \alpha_j^2+\delta\alpha} \label{e7}
    \end{eqnarray}
  \item ${\cal P} \longrightarrow {\cal V}$:
  $t,v,w,u,\{u_i\},\{\tilde{g_i}'\},\tilde{g}',g',m',\{\dot{t_i}\},\{\dot{v_i}\},\dot{v},\{\dot{w_i}\},\dot{w},
  i=1,...,n$
  \item ${\cal P} \longleftarrow {\cal V}$: challenges $\{c_i|i=1,...,n\}$, $c_i \in_U Z_q$
  \item ${\cal P} \longrightarrow {\cal V}$:
    \begin{eqnarray*}
    s        &=& \sum_{j=1}^n r_jc_j + \alpha \\
    s_i      &=& \sum_{j=1}^n A_{ij}c_j + \alpha_i \mbox{ mod }q, i=1,...,n \\
    \lambda' &=& \sum_{j=1}^n \lambda_jc_j^2 + \delta \mbox{ mod }q
    \end{eqnarray*}
  \item ${\cal V}$ verifies:
    \begin{eqnarray}
    \label{eqn:eqn7}
    \tilde{g}^s\prod_{j=1}^n \tilde{g_j}^{s_j}      &=& \tilde{g}'\prod_{j=1}^n \tilde{g_j}'^{c_j} \\
    \label{eqn:eqn8}
    g^s\prod_{j=1}^n g_j^{s_j}                      &=& g'\prod_{j=1}^n
    g_j'^{c_j} \\
    \label{eqn:eqn9}
    y^s\prod_{j=1}^n m_j^{s_j}                      &=& m'\prod_{j=1}^n m_j'^{c_j} \\
    g^{\lambda'}                                    &=& u\prod_{j=1}^n u_j^{c_j^2} \label{e8} \\
    t^{\lambda'}v^s g^{\sum_{j=1}^n (s_j^3-c_j^3)}  &=& \dot{v}\prod_{j=1}^n \dot{v_j}^{c_j}\dot{t_j}^{c_j^2} \label{e9} \\
    w^s g^{\sum_{j=1}^n (s_j^2-c_j^2)}  &=& \dot{w}\prod_{j=1}^n
    \dot{w_j}^{c_j} \label{e10}
    \end{eqnarray}
\end{enumerate}

\newpage
\heading{Intuition}
\bi
 \item (\ref{eqn:eqn5}),(\ref{eqn:eqn6}),(\ref{e1}),(\ref{e2}),(\ref{eqn:eqn7}),
 (\ref{eqn:eqn8}) and (\ref{eqn:eqn9}) show prover's knowledge of matrix
 $(A_{ij})$ and $\{r_i\}$ satisfying (\ref{eqn:eqn3}) and (\ref{eqn:eqn4})
 \item (\ref{e3}),(\ref{e4}),(\ref{e5}),(\ref{e8}) and (\ref{e9}) show $(A_{ij})$
 satisfying (\ref{eqn:eqn2})
 \item (\ref{e6}),(\ref{e7}),(\ref{e10}) show $(A_{ij})$ satisfying (\ref{eqn:eqn1})
 \item based on Theorem 1, $(A_{ij})$ is a permutation matrix
\ei

\newpage
\heading{Millimix}

It is efficient for small input batches because each mix server
needs $O(nlogn)$ exponentiations with low constant coefficient.\\
Each mix server simulates a pairwise permutation network. The mix
server proves the correctness of each of its switching gate using
the following verification protocol.

\newpage
\heading{Verification Protocol for Switching Gate}

Input is El Gamal ciphertexts $(\alpha_1,\beta_1)$,
$(\alpha_2,\beta_2)$ of plaintexts $m_1$, $m_2$ respectively.
Output is El Gamal ciphertexts $(\alpha_1',\beta_1')$,
$(\alpha_2',\beta_2')$ of plaintexts $m_1'$, $m_2'$ respectively.
The server proves statements:
\begin{itemize}
  \item Statement 1: $m_1m_2=m_1'm_2'$ using Plaintext Equivalent Proof
  (\emph{$PEP$}) for $(\alpha_1\alpha_2,\beta_1\beta_2)$
  and $(\alpha_1'\alpha_2',\beta_1'\beta_2')$.
  \item Statement 2: $m_1=m_1'$ OR $m_1=m_2'$ using DISjunctive Plaintext Equivalent Proof
  (\emph{$DISPEP$})
\end{itemize}
\underline{$PEP$} proves $(\alpha',\beta')$ is a re-encryption of
$(\alpha,\beta)$ by using Schnorr identification protocol
\bi
 \item Compute
 $(y_s,g_s)=((\alpha/\alpha')^{z}(\beta/\beta'),y^{z}g)$ as
 Schnorr public key
 \item $(\alpha',\beta')$ re-encrypts $(\alpha,\beta)$
 $\Leftrightarrow$ $\exists \gamma \in Z_q$:
 $(y_s,g_s)=((y^{z}g)^{\gamma},y^{z}g)$
 \item Prover uses Schnorr identification protocol to show that
 it knows $\gamma$
\ei $DISPEP$ proves $(\alpha_1,\beta_1)$ is a re-encryption of one
of $(\alpha_1',\beta_1')$ and $(\alpha_2',\beta_2')$ by using
Disjunctive Schnorr identification protocol. Proof in
\cite{Jakobsson99-2}:
\bi
 \item Compute $(y_{s1},g_{s1})=(\alpha_1/\alpha_1',\beta_1/\beta_1')$ and
 $(y_{s2},g_{s2})=(\alpha_1/\alpha_2',\beta_1/\beta_2')$ as Schnorr
 public keys
 \item Use Disjunctive Schnorr identification protocol to show
 knowledge of one of the Schnorr private keys, which is also the El
 Gamal private key $x$ of the ciphertexts
 \item This requires the mix-server to know the El Gamal private
 key $x$, which is not acceptable
 \item We will show a revised version of this protocol
 which uses the approach in $PEP$ and removes this problem
\ei
\textbf{Modified $DISPEP$:}\\
Compute
\begin{eqnarray*}
(y_{s1},g_{s1})&=&((\alpha_1/\alpha_1')^{z_1}(\beta_1/\beta_1'),y^{z_1}g)\\
(y_{s2},g_{s2})&=&((\alpha_1/\alpha_2')^{z_2}(\beta_1/\beta_2'),y^{z_2}g)
\end{eqnarray*}
as Schnorr public keys.\\
Assume w.l.o.g. that $(\alpha_1,\beta_1)$ is a re-encryption of
$(\alpha_1',\beta_1')$, then $\exists \gamma_1 \in Z_q$ such that
$(y_{s1},g_{s1})=((y^{z_1}g)^{\gamma_1},y^{z_1}g)$.\\
Mix-server uses Disjunctive Schnorr identification protocol with
$(y_{s1},g_{s1}),(y_{s2},g_{s2})$ to show that it knows
$\gamma_1$.

\newpage
\heading{Attacking Furukawa-Sako01 Scheme}

Break correctness with a success chance of at least 50\%\\
Let $a$ be a generator of $Z_p$, then $a^{kq} \neq 1$ and
$a^{2kq}=1$. The mix server modifies one of the output ciphertexts
as
\begin{eqnarray*}
g_{i_0}' & = & g^{r_{i_0}}g_{\phi^{-1}(i_0)}\\
m_{i_0}' & = & y^{r_{i_0}}m_{\phi^{-1}(i_0)}a^{kq}
\end{eqnarray*}\\
Modifying $m_{i_0}'$ only affects equation (\ref{eqn:eqn9}) in
verification protocol\\
If $c_{i_0}$ is even, $a^{c_{i_0}kq}=1$. So
\[m_{i_0}'^{c_{i_0}}=(y^{r_{i_0}}m_{\phi^{-1}(i_0)}a^{kq})^{c_{i_0}}
=(y^{r_{i_0}}m_{\phi^{-1}(i_0)})^{c_{i_0}}\] Therefore, equation
(\ref{eqn:eqn9}) remains correct and the verification protocol
still accepts\\
In a similar way, the mix server can modify $g_{i_0}'$

\newpage
\heading{Countermeasure}

$m_{i_0}' \notin G_q$. So the attack can be detected by checking
whether $g_i', m_i' \in G_q$, $i=1,...,n$\\
If $k=1$, it requires one extra modular multiplication. If $k \neq
1$, two extra modular exponentiations are required

\newpage
\heading{Security}

The attack only affects Lemma \ref{lem:lem1} in \cite{Furukawa01}.
We show the short-coming of the original proof and how the fix
completes the proof.
\begin{lemma} \label{lem:lem1}
Assume ${\cal P}$ knows $\{A_{ij}\},\{r_i\},\{\alpha_i\}$ and
$\alpha$ satisfying (\ref{eqn:eqn5}) and (\ref{eqn:eqn6}), and
$\{s_i\}$ and $s$ satisfying (\ref{eqn:eqn7}). If (\ref{eqn:eqn8})
and (\ref{eqn:eqn9}) hold with non-negligible probability, then
either the relationships
\begin{displaymath}
\left\{ \begin{array}{llll}
    g'   &=& g^{\alpha}\prod_{j=1}^n g_j^{\alpha_j} \\
    g_i' &=& g^{r_i}\prod_{j=1}^n g_j^{A_{ji}}, i=1,...,n \\
    m'   &=& y^{\alpha}\prod_{j=1}^n m_j^{\alpha_j} \\
    m_i' &=& y^{r_i}\prod_{j=1}^n m_j^{A_{ji}}, i=1,...,n \\
\end{array} \right.
\end{displaymath}
hold or ${\cal P}$ can generate nontrivial integers $\{a_i\}$ and
$a$ satisfying $\tilde{g}^a \prod_{i=1}^n \tilde{g_i}^{a_i}=1$
with overwhelming probability.
\end{lemma}
\underline{Proof} Replace $\tilde{g'}$ and $\{\tilde{g_i'}\}$ in
(\ref{eqn:eqn7}) by those in (\ref{eqn:eqn5}) and
(\ref{eqn:eqn6}):
\[\tilde{g}^{\sum_{j=1}^n r_jc_j+\alpha-s}\prod_{i=1}^n \tilde{g_i}^{\sum_{j=1}^n A_{ij}c_j+\alpha_i-s_i}=1\]
Therefore, either
\begin{displaymath}
\left\{ \begin{array}{ll}
s   = \sum_{j=1}^n r_jc_j+ \alpha \\
s_i = \sum_{j=1}^n A_{ij}c_j+ \alpha_i \\
\end{array} \right.
\end{displaymath}
hold or ${\cal P}$ can generate nontrivial integers $\{a_i\}$ and
$a$ satisfying $\tilde{g}^a \prod_{i=1}^n \tilde{g_i}^{a_i}=1$\\
Replace $s$ and $\{s_i\}$ in (\ref{eqn:eqn8}):
\begin{eqnarray} \label{eqn:eqn10}
1=b_0 \prod_{i=1}^n b_i^{c_i}
\end{eqnarray}
where
\begin{eqnarray*}
b_0 &=& \frac{g^{\alpha}\prod_{j=1}^n g_j^{\alpha_j}}{g'}\\
b_i &=& \frac{g^{r_i}\prod_{j=1}^n g_j^{A_{ji}}}{g_i'}, i=1,...,n
\end{eqnarray*}\\
At this point, proof in \cite{Furukawa01} concludes $b_i=1,
i=0,...,n$. However, it is only correct if $b_i \in G_q$

\newpage
\heading{Millimix Attack}

An attack similar to one against Furukawa-Sako01 mix-net can be
applied to Millimix.\\
A second attack exploits the fact that the exponents $z$ in $PEP$
and $z_1,z_2$ in $DISPEP$ can be arbitrarily chosen. Let
$(\alpha_1,\beta_1)$ and $(\alpha_2,\beta_2)$ be input to a
switching gate of a malicious mix-server. The server computes
output as follows.
\begin{eqnarray*}
(\alpha_1',\beta_1') &=& (\alpha_1y^{-r_1-s_1z_1}g^{-s_1}, \beta_1g^{-r_1})\\
(\alpha_2',\beta_2') &=& (\alpha_2y^{-r_2+s_1z_1-sz}g^{s_1-s},
\beta_2g^{-r_2})
\end{eqnarray*}
Using $PEP$ and $DISPEP$ the server can still show that: $(i)$
$(\alpha_1'\alpha_2',\beta_1'\beta_2')$ is the re-encryption of
$(\alpha_1\alpha_2,\beta_1\beta_2)$, and $(ii)$ either
$(\alpha_1',\beta_1')$ or $(\alpha_2',\beta_2')$ re-encrypts
$(\alpha_1,\beta_1)$. To show $(i)$, the server computes
\begin{eqnarray*}
(\alpha/\alpha',\beta/\beta') &=&
(\alpha_1\alpha_2/\alpha_1'\alpha_2',\beta_1\beta_2/\beta_1'\beta_2')\\
                              &=& (y^{r_1+r_2+sz}g^{s},g^{r_1+r_2})\\
(y_s,g_s) &=& ((\alpha/\alpha')^z(\beta/\beta'),y^zg) =
((y^zg)^{r_1+r_2+sz},y^zg) \\
          &=& (g_s^{r_1+r_2+sz},g_s)
\end{eqnarray*}
Now Schnorr identification protocol will be performed as follows.
\begin{enumerate}
  \item ${\cal P} \longrightarrow {\cal V}$: a commitment $w=g_s^{e}$
  \item ${\cal P} \longleftarrow {\cal V}$: a challenge $c$
  \item ${\cal P} \longrightarrow {\cal V}$: a response $s=e+c(r_1+r_2+sz)$
\end{enumerate}
${\cal V}$ then check if $g_s^{s}=wy_s^{c}$. This equation is
correct and $PEP$ has been broken.\\
To show $(ii)$, we note that
\begin{eqnarray*}
(y_{s1},g_{s1}) &=&
((\alpha_1/\alpha_1')^{z_1}(\beta_1/\beta_1'),y^{z_1}g) =((y^{z_1}g)^{r_1+s_1z_1},y^{z_1}g) \\
          &=& (g_{s1}^{r_1+s_1z_1},g_{s1})
\end{eqnarray*}
Disjunctive Schnorr identification protocol can be performed as
follows.
\begin{enumerate}
  \item ${\cal P} \longrightarrow {\cal V}$: two commitments
  $w_1=g_{s1}^{e_1}$, $w_2=g_{s2}^{s_2}y_{s2}^{-c_2}$
  \item ${\cal P} \longleftarrow {\cal V}$: a challenge $c$
  \item ${\cal P} \longrightarrow {\cal V}$: responses
  $s_1=e_1+c_1(r_1+s_1z_1)$, $s_2$, $c_1=c\oplus c_2$, $c_2$
\end{enumerate}
${\cal V}$ then check that $g_{si}^{s_i}=w_iy_{si}^{c_i}$, $i=1,2$
holds

\newpage
\heading{Countermeasure}

$z$ must be either chosen by the verifier after the switching gate
has produced output. Or in non-interactive version, prover
provides $(z,c,s)$. A verifier then verifies
\begin{eqnarray*}
z &\stackrel{?}=& H(\alpha'\parallel \beta'\parallel \alpha \parallel \beta) \mbox{ mod } q \\
c &\stackrel{?}=& H(g' \parallel y' \parallel g'^sy'^c) \mbox{ mod
} q
\end{eqnarray*}
where $(y',g')=((\alpha/\alpha')^{z}(\beta/\beta'),y^{z}g)$ and
$H:\{0,1\}^{*} \rightarrow 2^{|q|}$ is a hash function\\
$DISPEP$ can be modified similarly. Both $z_1$ and $z_2$ must be
either chosen by the verifier after the switching gate has
produced the output, or computed as $z_1=z_2=H(\alpha_1'
\parallel \beta_1'
\parallel \alpha_2' \parallel \beta_2' \parallel \alpha_1
\parallel \beta_1 \parallel \alpha_2 \parallel \beta_2 )$.

\newpage
\heading{Security}

We show revised Lemma \ref{lem:lem2} in \cite{Jakobsson99-2} and
its proof, Lemma \ref{lem:lem3} in \cite{Jakobsson99-2} can be
revised similarly.
\begin{lemma} \label{lem:lem2}
Let $(\alpha,\beta)$ and $(\alpha',\beta')$ be two ciphertexts for
which $PEP$ produces \emph{accept} response.
\begin{itemize}
    \item if $z$ is chosen by the prover, then $(\alpha',\beta')$ is
    not necessarily a valid re-encryption of $(\alpha,\beta)$.
    \item if $z$ is chosen by the verifier or computed by hash
    function as shown above, then either $(\alpha',\beta')$ is a valid
    re-encryption of $(\alpha,\beta)$ or the prover can find the
    El Gamal private key $x$.
\end{itemize}
\end{lemma}
\newpage
\underline{Proof} Let $z$ be chosen by verifier. Suppose $K$ is
the set of $z \in Z_q$ such that prover knows $o \in Z_q$
satisfying $(\alpha/\alpha')^{z}(\beta/\beta')=(y^{z}g)^o$. The
probability that $PEP$ outputs \emph{accept} is $|K|/q$. With
sufficiently
large $q$, we can assume $|K|\geq 3$.\\
Assume distinct elements $z_0, z_1, z_2 \in K$. Let
$\alpha/\alpha'=g^u$ and $\beta/\beta'=g^v$. Prover knows $o_0,
o_1, o_2 \in Z_q$ satisfying
$(\alpha/\alpha')^{z_i}(\beta/\beta')=(y^{z_i}g)^{o_i}$, $i=0,1,2$
and so has the following system of three linear equations with
three unknowns $u$, $v$ and $x$:
\begin{displaymath}
\left\{ \begin{array}{lll}
z_0u+v-o_0z_0x&=&o_0\\
z_1u+v-o_1z_1x&=&o_1\\
z_2u+v-o_2z_2x&=&o_2\\
\end{array} \right.
\end{displaymath}
As $\alpha, \beta, \alpha', \beta' \in G_q$, then $u,v,x$ must
exist, and so the system must have a solution. If the solution is
unique, the prover will be able to solve it and find the value of
$x$ and that demonstrates a knowledge extractor for $x$.\\
On the other hand, if the system has more than one solution, the
following determinants are equal zero.
\begin{displaymath}
det=\left|\begin{array}{ccc}
z_0&1&-o_0z_0\\
z_1&1&-o_1z_1\\
z_2&1&-o_2z_2\\
\end{array}\right|=0
\end{displaymath}
\begin{displaymath}
det_x=\left|\begin{array}{ccc}
z_0&1&-o_0\\
z_1&1&-o_1\\
z_2&1&-o_2\\
\end{array}\right|=0
\end{displaymath}
This implies that,
\begin{eqnarray*}
0 & = & det + z_0det_x\\
  & = & (o_2-o_1)(z_0-z_1)(z_0-z_2)
\end{eqnarray*}
and so $o_2=o_1$. This leads to $u=vx$, which means that
$\alpha/\alpha'= (\beta/\beta')^x$ and so $(\alpha',\beta')$ is a
valid re-encryption of $(\alpha,\beta)$.\\
\begin{lemma} \label{lem:lem3}
Let $(\alpha_1,\beta_1)$, $(\alpha_1',\beta_1')$ and
$(\alpha_2',\beta_2')$ be ciphertexts for which $DISPEP$ produces
\emph{accept} response.
\begin{itemize}
    \item if $z_1$ and $z_2$ are chosen by the prover, then
    $(\alpha_1,\beta_1)$ is not necessarily a valid re-encryption of either
    $(\alpha_1',\beta_1')$ or $(\alpha_2',\beta_2')$.
    \item if $z_1$ and $z_2$ are chosen by the verifier or computed by hash
    function as shown above, then either $(\alpha_1,\beta_1)$ is a valid
    re-encryption of either $(\alpha_1',\beta_1')$ or $(\alpha_2',\beta_2')$
    or the prover can find the El Gamal private key $x$.
\end{itemize}
\end{lemma}

\newpage
\heading{Conclusion}
Two attacks against resilient mix-nets\\
Countermeasures and security and efficiency analysis\\
First attack against Furukawa-Sako01 mix-net can also be used
against a number of other mix-nets. It could have wider
implications proofs that are based on discrete logarithm
assumption\\
Second attack breaks the verification protocol of Millimix. It can
be countered by carefully choosing the challenge.

\newpage
\begin{thebibliography}{99}
\bibitem{Furukawa01} J. Furukawa and K. Sako. An Efficient Scheme for Proving a Shuffle, pages 368 ff.
J. Kilian (Ed.), CRYPTO 2001. LNCS 2139
\bibitem{Jakobsson99-2} M. Jakobsson and A. Juels.
Millimix: Mixing in small batches, 1999. DIMACS Technical Report
99-33.
\end{thebibliography}

\end{slide}
\end{document}