+\subsection{Analysis}
+
+We now examine the protocol in a more formal setting, with the objective of
+characterizing our requirements for the function $\oracle{H}$. Fix a
+\emph{group description} $\mathcal{G} = (G, q, g)$, where $G$ is a cyclic
+group of prime order $q$ generated by $g \in G$, and a function
+$\oracle{H}\colon \{ 0, 1 \}^* \to \{ 0, 1 \}^L$. Define the
+\emph{authentication oracle} $\oracle{O}_{\mathcal{G}, \oracle{H}}(\alpha, x,
+h)$, where $\alpha \in \mathbb{Z} / q \mathbb{Z}$, $x \in g$ and $h \in \{ 0,
+1 \}^L$, to return $x^\alpha$ if $h = \oracle{H}(x^\alpha)$ and the symbol
+$\bot$ otherwise.
+
+We introduce two experiments:
+\begin{tabular}[C]{@{}G|G@{}}
+ \begin{program}
+ \quad \= \quad \= \kill
+ Experiment $\expt{uni-cca}{A_{\text{cca}}, \oracle{H}}(\mathcal{G})$ \\
+ \> $\alpha, \tau \rgets \mathbb{Z}/q\mathbb{Z}$; \\
+ \> $R \gets
+ A_{\text{cca}}
+ ^{\oracle{O}_{\mathcal{G}, \oracle{H}}(\alpha, \cdot, \cdot),
+ \oracle{H}
+ (\cdot)}
+ (g^\alpha, g^\tau, \oracle{H}(g^{\alpha\tau}))$; \\
+ \> \textbf{if} $R = g^{\alpha\tau}$ \textbf{then} \textbf{return} $1$; \\
+ \> \textbf{else} \textbf{return} $0$;
+ \end{program}
+ &
+ \begin{program}
+ \quad \= \quad \= \kill
+ Experiment $\expt{uni-no}{A}(\mathcal{G})$ \\
+ \> $\alpha, \tau \rgets \mathbb{Z}/q\mathbb{Z}$; \\
+ \> $R \gets A(g^\alpha, g^\tau)$; \\
+ \> \textbf{if} $R = g^{\alpha\tau}$ \textbf{then} \textbf{return} $1$; \\
+ \> \textbf{else} \textbf{return} $0$;
+ \end{program}
+\end{tabular}
+We mandate that the adversary $A_{\text{cca}}$ never query its authentication
+oracle with the test challenge $g^\tau$.
+
+We will consider a function $\oracle{H}$ to be suitable for our purposes if
+for any adversary $A_{\text{cca}}$, there is an adversary $A$ for which the
+distributions of $\expt{uni-cca}{A_{\text{cca}}, \oracle{H}}(\mathcal{G})$
+and $\expt{uni-no}{A}(\mathcal{G})$ are computationally indistinguishable.
+Intuitively, this means that the authentication oracle isn't useful in
+attacking the protocol: any adversary which has access to an oracle can be
+replaced by one which has approximately the same probability of success but
+without oracle access.
+
+We first prove that a random oracle \cite{Bellare:1993:ROP} makes a
+`suitable' function.
+
+\begin{theorem}
+ If $\oracle{H}$ is a random oracle with $L$-bit output, where $L$ is some
+ polynomial function of the length of $q$, then, for any adversary
+ $A_{\text{cca}}$, there exists an adversary $A$ such that
+ \[ \expt{uni-cca}{A_{\text{cca}}, \oracle{H}}(\mathcal{G})
+ \compind \expt{uni-no}{A}(\mathcal{G}) \]
+\end{theorem}
+\begin{proof}
+ The idea behind the proof is that we construct an adversary $A$ in terms of
+ the given adversary $A_{\text{cca}}$ with the same output in all but
+ negligibly few cases.
+
+ Our adversary $A$ isn't provided with either oracle supplied to
+ $A_{\text{cca}}$.
+
+ Simulating the random oracle is easy. $A$ maintains a table, initially
+ empty, of pairs $(q, r)$. When the oracle is invoked on input $q$, we look
+ it up in the table: if there is some entry $(q, r)$, it returns $r$;
+ otherwise we toss coins to choose a new output $r$ and add $(q, r)$ to the
+ table. This is obviously a polynomial-time activity, since
+ $A_{\text{cca}}$ makes only polynomially many queries, and answering each
+ one takes polynomial time.
+
+ The authentication oracle is a little harder. Suppose $A_{\text{cca}}$
+ makes a query $(x, h)$. If there is an entry $(q, h)$ in the random oracle
+ table, the authentication oracle returns $q$; otherwise it returns $\bot$.