\xcalways\section{The Wrestlers Protocol}\x

\xcalways\subsection{Identification using Diffie-Hellman}\x

\begin{slide}
  \resetseq
  \head{Identification using Diffie-Hellman \seq: properties}
  \topic{properties}

  \begin{itemize}
  \item Simple -- easy to remember, analyse and implement
  \item Practical -- two scalar multiplications for each party
  \item Secure -- under Computational Diffie-Hellman assumption
  \item Zero-knowledge -- statistical ZK
  \item Proofs in random oracle model -- but without `programming'
  \end{itemize}
\end{slide}

\begin{slide}
  \head{Identification using Diffie-Hellman \seq: basic setting}
  \topic{setting}

  \begin{itemize}
  \item Cyclic group $(G, +)$
  \item $|G| = q$ is prime
  \item $P$ generates $G$
  \item Alice's private key is $a \inr \Nupto{q}$
  \item Alice's public key is $A = a P$
  \item Assume computational Diffie-Hellman problem hard in $G$
  \end{itemize}
\end{slide}

\begin{slide}
  \head{Identification using Diffie-Hellman \seq: na\"\i ve attempt}
  \topic{protocol design}

  \begin{protocol}
    Alice & Bob \\
    (Private key $a \inr \Nupto{q}$) & (Public key $A = a P$)
    \\[\medskipamount]
    & $r \getsr \Nupto{q}$; \\
    & $R \gets r P$; \\
    \\
    \\
    \\
    \send{<-}{R}
    $Y \gets a R$; \\
    \\
    \\
    \\
    \send{->}{Y}
    & \textbf{Check} $Y = r A$
  \end{protocol}
\end{slide}

\begin{slide}
  \head{Identification using Diffie-Hellman \seq: fix it with a hash}
  \protocolskip0pt

  \begin{protocol}
    Alice & Bob \\
    (Private key $a \inr \Nupto{q}$) & (Public key $A = a P$)
    \\[\medskipamount]
    & $r \getsr \Nupto{q}$; \\
    & $R \gets r P$; \\
    & $Y \gets r A$; \\
    & \diff $h \gets H(\cookie{check}, R, Y)$; \\
    & \\
    \send{<-}{(R, \hbox{\diff $h$})}
    $Y \gets a R$; \\
    \\
    \\
    \diff \textbf{Check} $h = H(\cookie{check}, R, Y)$ \\
    \send{->}{Y}
    & \textbf{Check} $Y$
  \end{protocol}
  \dots but there are still small-subgroup attacks
\end{slide}

\begin{slide}
  \head{Identification using Diffie-Hellman \seq: Stinson-Wu [SW06]}
  \protocolskip0pt

  \begin{protocol}
    Alice & Bob \\
    (Private key $a \inr \Nupto{q}$) & (Public key $A = a P$)
    \\[\medskipamount]
    & $r \getsr \Nupto{q}$; \\
    & $R \gets r P$; \\
    & $Y \gets r A$; \\
    & $h \gets H(\cookie{check}, R, Y)$; \\
    & \\
    \send{<-}{(R, h)}
    $Y \gets a R$; \\
    \\
    \diff \textbf{Check} $q R = 0$; \\
    \textbf{Check} $h = H(\cookie{check}, R, Y)$ \\
    \send{->}{Y}
    & \textbf{Check} $Y$
  \end{protocol}
  \dots and apply the Knowledge of Exponent assumption
\end{slide}

\begin{slide}
  \head{Identification using Diffie-Hellman \seq: the Wrestlers Protocol
  $\Wident$}

  \begin{protocol}
    Alice & Bob \\
    (Private key $a \inr \Nupto{q}$) & (Public key $A = a P$)
    \\[\medskipamount]
    & $r \getsr \Nupto{q}$; \\
    & $R \gets r P$; \\
    & $Y \gets r A$; \\
    & $h \gets H(\cookie{check}, R, Y)$; \\
    & \diff $c \gets h \xor r$; \\
    \send{<-}{(R, \hbox{\diff $c$})}
    $Y \gets a R$; \\
    $h \gets H(\cookie{check}, R, Y)$; \\
    \diff $r \gets c \xor h$; \\
    \diff \textbf{Check} $R = r P$ \\
    \send{->}{Y}
    & \textbf{Check} $Y$
  \end{protocol}
\end{slide}

\begin{slide}
  \head{Identification using Diffie-Hellman \seq: identification-based
  $\Wident$}

  \begin{protocol}
    Alice & Bob \\
    (Private key $K_A = t I_A$) &
    (Public key $I_A = H(\cookie{id}, \text{Alice})$)
    \\[\medskipamount]
    & $r \getsr \Nupto{q}$; \\
    & $R \gets r P$; \\
    & \diff $Y \gets \hat{e}(T, I_A)^r$; \\
    & $h \gets H(\cookie{check}, R, Y)$; \\
    & $c \gets h \xor r$; \\
    \send{<-}{(R, c)}
    \diff $Y \gets \hat{e}(R, K_A)$; \\
    $h \gets H(\cookie{check}, R, Y)$; \\
    $r \gets c \xor h$; \\
    \textbf{Check} $R = r P$ \\
    \send{->}{Y}
    & \textbf{Check} $Y$
  \end{protocol}
  (Trusted authority's private key $t \inr \Nupto{q}$; public key $T = t P$)
\end{slide}

\xcalways\subsection{Key exchange}\x

\begin{slide}
  \resetseq
  \head{Mutual identification \seq: Bob identifies Alice}
  \topic{mutual identification}

  \begin{protocol}
    Alice & Bob \\
    (Private key $a$, public key $A = a P$)
    \\[\medskipamount]
    & $r_B \getsr \Nupto{q}$; \\
    & $R_B \gets r_B P$; \\
    \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))}
    \\
    $Y_B \gets a R_B$; \\
    \\
    \send{->}{Y_B}
  \end{protocol}
\end{slide}
    
\begin{slide}
  \head{Mutual identification \seq: Alice identifies Bob too}

  \begin{protocol}
    Alice & Bob \\
    (Private key $a$, public key $A = a P$) &
    \other (Private key $b$, public key $B = b P$)
    \\[\medskipamount]
    \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\
    \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\
    \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))}
    \send{->}{\other (R_A, r_A \xor H(\cookie{check}, R_A, Y_A))}
    $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\
    \\
    \send{->}{Y_B}
    \send{<-}{\other Y_A}
  \end{protocol}
\end{slide}
    
\begin{slide}
  \head{Mutual identification \seq: key exchange?}

  \begin{protocol}
    Alice & Bob \\
    (Private key $a$, public key $A = a P$) &
    \other (Private key $b$, public key $B = b P$)
    \\[\medskipamount]
    \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\
    \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\
    \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))}
    \send{->}{\other (R_A, r_A \xor H(\cookie{check}, R_A, Y_A))}
    $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\
    \\
    \send{->}{Y_B}
    \send{<-}{\other Y_A}
    \diff $Z \gets r_A R_B$; & \diff $Z \gets r_B R_A$;
  \end{protocol}
  \bigskip
  Unfortunately it's not secure.
\end{slide}

\begin{slide}
  \resetseq
  \head{Key exchange \seq: properties}
  \topic{properties}

  \begin{itemize}
  \item Simple -- symmetrical; based on mutual identification
  \item Practical -- three, four or five flows; four multiplications by each
    party
  \item Secure -- provides SK-security in model of [CK01]
  \item Deniable -- simulator can produce convincing transcripts
  \item Proofs in random oracle model -- again without `programming'
  \end{itemize}
\end{slide}

\begin{slide}
  \head{Key exchange \seq: setting}
  \topic{setting}

  \begin{itemize}
  \item Cyclic group $(G, +)$
  \item $|G| = q$ is prime
  \item $P$ generates $G$
  \item Alice's private key is $a \inr \Nupto{q}$; her public key is $A = a
    P$
  \item Bob's private key is $b \inr \Nupto{q}$; his public key is $B = b
    P$
  \item Symmetric IND-CCA encryption scheme $\E = (\kappa, E, D)$
  \item Assume computational Diffie-Hellman problem hard in $G$
  \end{itemize}
\end{slide}

\begin{slide}
  \head{Key exchange \seq: broken first attempt}
  \topic{protocol design}

  \begin{protocol}
    Alice & Bob \\
    (Private key $a$, public key $A = a P$) &
    \other (Private key $b$, public key $B = b P$)
    \\[\medskipamount]
    \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\
    \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\
    \\
    \\
    \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))}
    \send{->}{\other (R_A, r_A \xor H(\cookie{check}, R_A, Y_A))}
    $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\
    $Z \gets r_A R_B$; & $Z \gets r_B R_A$; \\
    \send{->}{(R_A, Y_B)}
    \send{<-}{\other (R_B, Y_A)}
    Key is $Z$ & Key is $Z$
  \end{protocol}
\end{slide}

\begin{slide}
  \head{Key exchange \seq: solution -- encrypt responses}

  \begin{protocol}
    Alice & Bob \\
    (Private key $a$, public key $A = a P$) &
    \other (Private key $b$, public key $B = b P$)
    \\[\medskipamount]
    \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\
    \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\
    \\
    \\
    \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))}
    \send{->}{\other (R_A, r_A \xor H(\cookie{check}, R_A, Y_A))}
    $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\
    \diff $(K_0, K_1) \gets H(\cookie{key}, r_A R_B)$; &
    \diff $(K_0, K_1) \gets H(\cookie{key}, r_B R_A)$; \\
    \send{->}{(R_A, \hbox{\diff $E_{K_0}(Y_B)$})}
    \send{<-}{\other (R_B, \hbox{\diff $E_{K_0}(Y_A)$})}
    Key is $K_1$ & Key is $K_1$
  \end{protocol}
\end{slide}

\begin{slide}
  \head{Key exchange \seq: multiple sessions}

  \begin{protocol}
    Alice & Bob \\
    (Private key $a$, public key $A = a P$) &
    \other (Private key $b$, public key $B = b P$)
    \\[\medskipamount]
    \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\
    \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\
    \\
    \\
    \send{<-}{(R_B, r_B \xor H(\cookie{check},
      \hbox{\diff $B$}, \hbox{\diff $s$}, R_B, Y_B))}
    \send{->}{\other (R_A, r_A \xor H(\cookie{check},
      \hbox{\diff $A$}, \hbox{\diff $s$}, R_A, Y_A))}
    $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\
    $(K_0, K_1) \gets H(\cookie{key}, r_A R_B)$; &
    $(K_0, K_1) \gets H(\cookie{key}, r_B R_A)$; \\
    \send{->}{(R_A, E_{K_0}(Y_B))}
    \send{<-}{\other (R_B, E_{K_0}(Y_A))}
    Key is $K_1$ & Key is $K_1$
  \end{protocol}
  (Session id is $s$)
\end{slide}

\begin{slide}
  \head{Key exchange \seq: proof sketch}

  \begin{itemize}
  \item $\G0$ is SK-security game.
  \item In $\G1$, stop game unless all parties have distinct public keys
    (collision bound).
  \item In $\G2$, use extractor to answer challenges other than from matching
    session.
  \item In $\G3$, stop game if adversary queries $H(\cookie{key}, r_A r_b P)$
    (CDH in $G$).
  \item In $\G4$, stop game if session accepts response except from matching
    session.
    \begin{itemize}
    \item In $\G5$, focus on a single session (factor of $q_S$).
    \item In $\G6$, encrypt $1^{|Y|}$ instead of $Y = x R$ (IND-CCA of $\E$).
    \item In $\G7$, focus on a single party (factor of $n$).
    \item Now if party accepts, reduce from impersonating in $\Wident$.
    \end{itemize}
  \end{itemize}
\end{slide}

\begin{slide}
  \head{Key exchange \seq: security result}
  \begin{spliteqn*}
    \InSec{sk}(\Wkx^{G, \E}; t, n, q_S, q_M, q_I, q_K) \le
      2 q_S \bigl( \InSec{ind-cca}(\E; t', q_M, q_M) + {} \\
      \InSec{mcdh}(G; t', q_K) +
      n \,\InSec{mcdh}(G; t', q_M + q_I) \bigr) + {} \\
      \frac{n (n - 1)}{|G|} +
      \frac{2 q_M}{2^{\ell_I}}.
  \end{spliteqn*}
  \begin{multicols}{2}
    \begin{itemize}
    \item $t$ is running time of adversary
    \item $n$ is number of parties
    \item $q_S$ is number of new sessions
    \item $q_M$ is number of messages sent
    \item $q_I$ is number of $H(\cookie{check}, \cdot)$ queries
    \item $q_K$ is number of $H(\cookie{key}, \cdot)$ queries
    \item $t' = t + O(q_S) + O(q_M q_I) + O(q_K)$
    \end{itemize}
  \end{multicols}
\end{slide}

\begin{slide}
  \head{Key exchange \seq: fully deniable variant}

  \begin{protocol}
    Alice & Bob \\
    (Private key $a$, public key $A = a P$) &
    \other (Private key $b$, public key $B = b P$)
    \\[\medskipamount]
    \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\
    \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\
    \send{->}{\diff R_A}
    \send{<-}{\diff R_B}
    \send{<-}{(R_B, r_B \xor H(\cookie{check}, B, s, \hbox{\diff $R_A$}, R_B, Y_B))}
    \send{->}{\other (R_A, r_A \xor H(\cookie{check}, A, s, \hbox{\diff $R_B$}, R_A, Y_A))}
    $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\
    $(K_0, K_1) \gets H(\cookie{key}, r_A R_B)$; &
    $(K_0, K_1) \gets H(\cookie{key}, r_B R_A)$; \\
    \send{->}{(R_A, E_{K_0}(Y_B))}
    \send{<-}{\other (R_B, E_{K_0}(Y_A))}
    Key is $K_1$ & Key is $K_1$
  \end{protocol}
\end{slide}

\endinput

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "wrslides"
%%% End: 
