+\begin{theorem}
+ Assuming that the Diffie-Hellman problem is hard in $G$, no probabilistic
+ polynomial-time adversary can impersonate in the Wrestlers Authentication
+ Protocol with random oracle with better than negligible probability.
+ \label{thm:wap-dhp}
+\end{theorem}
+\begin{proof}
+ \newcommand{\Hlist}{\textit{$\oracle{H}$-list}}
+ \newcommand{\Hqueries}{\textit{$\oracle{H}$-queries}}
+ \newcommand{\Hsim}{\textit{$\oracle{H}$-sim}}
+ \renewcommand{\H}{\oracle{H}}
+ %
+ We prove the theorem by contradiction. Given a polynomial-time adversary
+ $A$ which impersonates Alice with non-negligible probability $\epsilon$, we
+ construct an adversary which solves the Diffie-Hellman problem with
+ probability no less than $\epsilon \poly{k}$, i.e.,
+ \[ \Pr[A'(g^\alpha, g^\beta) = g^{\alpha\beta}] \ge \epsilon \poly{k}. \]
+ Thus, if there is any polynomial-time $A$ which impersonates with better
+ than negligible probability, then there is a polynomial-time $A'$ which
+ solves Diffie-Hellman with essentially the same probability, which would
+ violate our assumption of the hardness of Diffie-Hellman.
+
+ The idea behind the proof is that the check value is only useful to $A$
+ once it has discovered the correct response to the challenge, which it must
+ have done by solving the Diffie-Hellman problem. Hence, our Diffie-Hellman
+
+ \begin{figure}
+ \begin{program}
+ \quad \= \kill
+ Adversary $A'(a, b)$: \+ \\
+ $\Hlist \gets \emptyset$; \\
+ $\Hqueries \gets \emptyset$; \\
+ $r \getsr \{ 0, 1 \}^k$; \\
+ $x \gets A^{\Hsim(\cdot)}(a, b, r)$; \\
+ $c \getsr (\Hlist \cup \{ x \}) \cap G$; \\
+ \textbf{return} $c$; \- \\[\medskipamount]
+ %
+ Simulated random oracle $\Hsim(q)$: \+ \\
+ \textbf{if} $\exists r : (q, r) \in \Hlist$
+ \textbf{then} \textbf{return} $r$; \\
+ $r \gets \{ 0, 1 \}^k$; \\
+ $\Hlist \gets \Hlist \cup \{ (q, r) \}$; \\
+ $\Hqueries \gets \Hqueries \cup \{ q \}$; \\
+ \textbf{return} $r$;
+ \end{program}
+ %
+ \caption{The algorithm for the proof of theorem~\ref{thm:wap-dhp}}
+ \label{fig:wap-dhp-rdc}
+ \end{figure}
+
+ The adversary $A'$ is shown in figure~\ref{fig:wap-dhp-rdc}. It generates
+ a random check-value and runs the impersonator $A$.
+
+ The simulated random oracle $\Hsim$ gathers together the results of all of
+ the random oracle queries made by $A$. The final result returned by $A'$
+ is randomly chosen from among all of the `plausible' random oracle queries
+ and $A$'s output, i.e., those queries which are actually members of the
+ group. The check value given to $A$ is most likely incorrect (with
+ probability $1 - 2^{-k}$): the intuition is that $A$ can only notice if it
+ actually computes the right answer and then checks explicitly.
+
+ If $A$ does compute the correct answer $g^{\alpha\beta}$ and either returns
+ it or queries $\Hsim$ on it, then $A'$ succeeds with probability $\epsilon
+ / |(\Hlist \cup \{ x \}) \cap G| = \epsilon \poly{k}$, since $|\Hlist|$ is
+ no greater than the number of random oracle queries made by $A$ (which must
+ be polynomially bounded).\footnote{%
+ This polynomial factor introduces a loss in the perceived security of the
+ authentication protocol. It appears that this loss is only caused by the
+ possibility of the adversary $A$ being deliberately awkward and checking
+ the value of $c$ after having computed the answer. However, we can't see
+ a way to improve the security bound on the scheme without imposing
+ artificial requirements on $A$.} %
+
+ It remains to show that if $A$ never queries its random oracle on
+ $g^{\alpha\beta}$ then it cannot distinguish the random check value $r$
+ from the correct one $\beta \xor \H(g^{\alpha\beta})$, and hence won't
+ notice that $A'$ is lying to it. But this is obvious: $A$'s probability of
+ guessing the random value that would have been returned had it actually
+ queried $\Hsim$ on the input $g^{\alpha\beta}$ is equal to the probability
+ of it guessing $\beta \xor r$ instead, since $\Hsim$ chooses its responses
+ uniformly at random. This completes the proof.
+\end{proof}
~mdw / tripe / commitdiff