wrestlers.tex: Let `\section' act as a section header in the source.

[doc/wrestlers] / wr-main.tex

\section{The Wrestlers Protocol}
\frame{\tableofcontents[currentsection]}

\subsection{Identification using Diffie-Hellman}

\begin{frame}{Identification using Diffie-Hellman: 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{frame}

\begin{frame}{Identification using Diffie-Hellman: basic 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{frame}

\begin{frame}{Identification using Diffie-Hellman: protocols}
  %% Overlays:
  %%   1 - basic setup (alice's keys)
  %% naïve version
  %%   2 - bob makes eqphemeral keys
  %%   3 - bob sends challenge to alice
  %%   4 - alice computes response and sends it back
  %%   5 - bob computes expected answer
  %%   6 - bob checks alice's response
  %%   7 - remark?
  %% hash fix (8)
  %%   9 - bob computes check hash and sends it
  %%  10 - alice verifies the hash
  %%  11 - remark?
  %% stinson-wu (12)
  %%  13 - check subgroup membership
  %%  14 - don't hash U
  %%  15 - remark?
  %% wrestlers (16)
  %%  17 - bob computes and sends c
  %%  18 - alice recovers and checks u
  \begin{protocol}{5}{16}
    \node [alice, thoughts] at (0, 2)
            {Private: $a \inr \Nupto{q}$ \\
             Public: $A = a P$};
    \uncover<2->{
      \node [bob, thoughts] at (0, 4)
              {{$u \getsr \Nupto{q}$; \\
               $U \gets u P$; \\
               \action<5->{$Y \gets u A$;} \\
               \action<9-| alert@9-11>{$
                 h \gets H(\cookie{check},
                   \only<9-13,16->{U, Y}
                   \action<alert@14-15| only@14-15>{Y})
               $;} \\
               \action<17-| alert@17-> {
                 $c \gets u \xor h$;
               }
             }};
    }
    \uncover<3->{
      \path [message, ->] (0, 10) -- node [above]
              {{\vphantom{$,$}
                \only<3-8>{$U$}
                \only<9-16>{$U, \alert<9-11>{h}$}
                \only<17->{$U, \alert<17->{c}$}  }}
              +(1, 0);
    }
    \uncover<4->{
      \node [alice, thoughts] at (0, 10)
              {{$Y' \gets a U$; \\
                \action<only@10-16| alert@10-11>
                  {Check $h = H(\cookie{check},
                     \only<10-13,16->{U, Y}
                     \action<alert@14-15| only@14-15>{Y})
                   $; \\}
                 \only<17->
                   {$h' \gets H(\cookie{check}, U, Y)$; \\}
                \action<only@13-15| alert@13-15>{Check $q U = 0$;}
                \action<only@18-| alert@18->{
                  $r' \gets h' \xor c$; \\
                  Check $r' P = U$;
                }}};
      \path [message, <-] (0, 14) -- node [above] {$Y'$} +(1, 0);
    }
    \uncover<6->{
      \node [bob, thoughts] at (0, 14) {Check $Y = Y'$;};
    }
  \end{protocol}
  \par\vskip-\bigskipamount
  \begin{itemize}
  \item<only@2-7> Naïve attempt
    \only<7>{-- lots of attacks against this protocol.}
  \item<only@8-11> Fix it with a hash
    \only<11>{-- still open to small-subgroup attacks.}
  \item<only@12-15> Stinson-Wu [SW06]
    \only<15>{-- and assume Knowledge of Exponent.}
  \item<only@16-> The Wrestlers identification protocol $\Wident$.
  \end{itemize} \par
\end{frame}

\subsection{Key exchange}

\begin{frame}{Mutual identification: protocol}
  \begin{protocol}{4}{14}
    \node [alice, thoughts] at (0, 2)
      {\footnotesize Private $a$; public $A = a P$};

    \node [bob, thoughts] at (0, 3)
          {{ $u \getsr \Nupto{q}$; \\
             $U \gets u P$;
             $Y_B \gets u A$; }};
    \path [message, ->] (0, 5.5) -- node [above]
          {$U, u \xor H(\cookie{check}, U, Y_B$)}
          +(1, 0);

    \node [alice, thoughts] at (0, 8)
          {{ $Y'_B \gets a U$; }};
    \path [message, <-] (0, 9) -- node [above]
          {$Y'_B$}
          +(1, 0);

    \only<2->{
      \node [bob, other, thoughts] at (0, 2)
        {\footnotesize Private $b$; public $B = b P$};

      \node [alice, other, thoughts] at (0, 3)
            {{ $v \getsr \Nupto{q}$; \\
               $V \gets v P$;
               $Y_A \gets v B$; }};
      \path [message, other, <-] (0, 7) -- node [above]
            {$V, v \xor H(\cookie{check}, V, Y_A$)}
            +(1, 0);

      \node [bob, other, thoughts] at (0, 8)
            {{ $Y'_A \gets b V$; }};
      \path [message, other, ->] (0, 10.5) -- node [above]
            {$Y'_A$}
            +(1, 0);
    }
    \action<3-| alert@3->{
      \node [bob, thoughts] at (0, 11) {$Z \gets u V = u v P$;};
      \node [alice, thoughts] at (0, 11) {$Z \gets v U = u v P$;};
    }
  \end{protocol}
  \par\vskip-\bigskipamount
  \begin{itemize}
  \item<3-> We can do ephemeral Diffie-Hellman with the challenges!
  \item<4-> Unfortunately, it's not secure.
  \end{itemize}
\end{frame}

\begin{frame}{Key exchange: 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{frame}

\begin{frame}{Key exchange: 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{frame}

\begin{frame}{Key exchange: protocols}
  %% overlays
  %%  1 - original broken protocol
  %%  2 - encrypt responses
  %%  3 - session-ids
  %%  4 - pre-challenges
  \begin{protocol}{3.9}{17}
    \node [alice, thoughts] at (0, 1.5)
      {\footnotesize Private $a$; public $A = a P$};

    \node [bob, thoughts] at (0, 3)
          {{ $u \getsr \Nupto{q}$; \\
             $U \gets u P$;
             $Y_B \gets u A$; }};
    \only<4->
      {\path [message, ->] (0, 6) -- node [above] {$\alert<4>{U}$} +(1, 0);}
    \path [message, ->] (0, 9) -- node [above]
          {$U, u \xor H(\cookie{check},
            \only<3->{\alert<3>{B}, \alert<3>{s},}
            \only<4->{\alert<4>{V},}
            U, Y_B$)}
          +(1, 0);

    \node [alice, thoughts] at (0, 11)
          {{\strut
            \only<1>{$Z \gets v U$; \\}%
            \action<only@2-| alert@2>
              {$(K, \hat{K}) \gets H(\cookie{key}, v U)$; \\}%
            $Y'_B \gets a U$; }};
    \path [message, <-] (0, 13.5) -- node [above]
          {$\action<only@2-| alert@2>{E_{\hat{K}}(}
            Y'_B
            \action<only@2-| alert@2>{)}$}
          +(1, 0);

    \node [bob, other, thoughts] at (0, 1.5)
      {\footnotesize Private $b$; public $B = b P$};

    \node [alice, other, thoughts] at (0, 3)
          {{ $v \getsr \Nupto{q}$; \\
             $V \gets v P$;
             $Y_A \gets v B$; }};
    \only<4->
      {\path [message, other, <-] (0, 7.5) --
              node [above] {$\alert<4>{V}$} +(1, 0);}
    \path [message, other, <-] (0, 10.5) -- node [above]
          {$V, v \xor H(\cookie{check},
            \only<3->{\alert<3>{A}, \alert<3>{s},}
            \only<4->{\alert<4>{U},}
            V, Y_A$)}
          +(1, 0);

    \node [bob, other, thoughts] at (0, 11)
          {{\strut
            \only<1>{$Z \gets u V$; \\}%
            \action<only@2-| alert@2>
              {$(K, \hat{K}) \gets H(\cookie{key}, u V)$; \\}%
            $Y'_A \gets b V$; }};
    \path [message, other, ->] (0, 15) -- node [above]
          {${\action<only@2-| alert@2>{E_{\hat{K}}(}}
            Y'_A
            {\action<only@2-| alert@2>{)}}$}
          +(1, 0);
    \node [bob, thoughts] at (0, 15.5) {Use key $K$;};
    \node [alice, thoughts] at (0, 15.5) {Use key $K$;};
  \end{protocol}
\end{frame}

\endinput


\begin{frame}
  \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 $u_A \getsr \Nupto{q}$; & $u \getsr \Nupto{q}$; \\
    \other $U_A \gets u_A P$ & $U \gets u P$; \\
    \\
    \\
    \send{<-}{(U, u \xor H(\cookie{check}, U, Y_B))}
    \send{->}{\other (U_A, u_A \xor H(\cookie{check}, U_A, Y_A))}
    $Y_B \gets a U$; & \other $Y_A \gets b U$; \\
    $Z \gets u_A U$; & $Z \gets u U_A$; \\
    \send{->}{(U_A, Y_B)}
    \send{<-}{\other (U, Y_A)}
    Key is $Z$ & Key is $Z$
  \end{protocol}
\end{frame}

\begin{frame}
  \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 $u_A \getsr \Nupto{q}$; & $u \getsr \Nupto{q}$; \\
    \other $U_A \gets u_A P$ & $U \gets u P$; \\
    \\
    \\
    \send{<-}{(U, u \xor H(\cookie{check}, U, Y_B))}
    \send{->}{\other (U_A, u_A \xor H(\cookie{check}, U_A, Y_A))}
    $Y_B \gets a U$; & \other $Y_A \gets b U$; \\
    \diff $(K_0, K_1) \gets H(\cookie{key}, u_A U)$; &
    \diff $(K_0, K_1) \gets H(\cookie{key}, u U_A)$; \\
    \send{->}{(U_A, \hbox{\diff $E_{K_0}(Y_B)$})}
    \send{<-}{\other (U, \hbox{\diff $E_{K_0}(Y_A)$})}
    Key is $K_1$ & Key is $K_1$
  \end{protocol}
\end{frame}

\begin{frame}
  \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 $u_A \getsr \Nupto{q}$; & $u \getsr \Nupto{q}$; \\
    \other $U_A \gets u_A P$ & $U \gets u P$; \\
    \\
    \\
    \send{<-}{(U, u \xor H(\cookie{check},
      \hbox{\diff $B$}, \hbox{\diff $s$}, U, Y_B))}
    \send{->}{\other (U_A, u_A \xor H(\cookie{check},
      \hbox{\diff $A$}, \hbox{\diff $s$}, U_A, Y_A))}
    $Y_B \gets a U$; & \other $Y_A \gets b U$; \\
    $(K_0, K_1) \gets H(\cookie{key}, u_A U)$; &
    $(K_0, K_1) \gets H(\cookie{key}, u U_A)$; \\
    \send{->}{(U_A, E_{K_0}(Y_B))}
    \send{<-}{\other (U, E_{K_0}(Y_A))}
    Key is $K_1$ & Key is $K_1$
  \end{protocol}
  (Session id is $s$)
\end{frame}

\begin{frame}
  \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}, u_A u 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 U$ (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{frame}

\begin{frame}
  \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{frame}

\begin{frame}
  \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 $u_A \getsr \Nupto{q}$; & $u \getsr \Nupto{q}$; \\
    \other $U_A \gets u_A P$ & $U \gets u P$; \\
    \send{->}{\diff U_A}
    \send{<-}{\diff U}
    \send{<-}{(U, u \xor H(\cookie{check}, B, s, \hbox{\diff $U_A$}, U, Y_B))}
    \send{->}{\other (U_A, u_A \xor H(\cookie{check}, A, s, \hbox{\diff $U$}, U_A, Y_A))}
    $Y_B \gets a U$; & \other $Y_A \gets b U$; \\
    $(K_0, K_1) \gets H(\cookie{key}, u_A U)$; &
    $(K_0, K_1) \gets H(\cookie{key}, u U_A)$; \\
    \send{->}{(U_A, E_{K_0}(Y_B))}
    \send{<-}{\other (U, E_{K_0}(Y_A))}
    Key is $K_1$ & Key is $K_1$
  \end{protocol}
\end{frame}

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