index 9916a18..3f53936 100644 (file)
@@ -50,7 +50,7 @@ in \cite{Abdalla:2001:DHIES}.
\item a probabilistic \emph{key-generation} algorithm~$G$, which takes no
input (or a security parameter for asymptotic types) and returns a pair
$(P, K)$;
\item a probabilistic \emph{key-generation} algorithm~$G$, which takes no
input (or a security parameter for asymptotic types) and returns a pair
$(P, K)$;
-  \item a probabilistic \emph{exchange} algorithm~$X$, which is given a
+  \item a probabilistic \emph{exchange} algorithm~$E$, which is given a
as input a public key~$P$ and returns a \emph{public value}~$y$ and a
\emph{hash} $h \in \{0, 1\}^k$; and
\item a deterministic \emph{recovery} algorithm~$R$, which is given as
as input a public key~$P$ and returns a \emph{public value}~$y$ and a
\emph{hash} $h \in \{0, 1\}^k$; and
\item a deterministic \emph{recovery} algorithm~$R$, which is given as
@@ -235,18 +235,17 @@ in \cite{Abdalla:2001:DHIES}.
scheme is \emph{malleable} in a group of composite order.  For example,
suppose that $q = 2r$ for some $r$; then if $\alpha$ is even, we have
$(b\cdot g^r)^\alpha = b^\alpha$.  Passing $b$ to the oracle ensures that
scheme is \emph{malleable} in a group of composite order.  For example,
suppose that $q = 2r$ for some $r$; then if $\alpha$ is even, we have
$(b\cdot g^r)^\alpha = b^\alpha$.  Passing $b$ to the oracle ensures that
-  these queries are given independent answers, even if the shared secret is
-  the same.
+  these queries given independent answers, even if the shared secret is the
+  same.
\end{slide}

\begin{proof}
Suppose that $A$ solves the oracle hash decision problem for
$\Xid{\mathcal{K}}{DH}^{G, H}$.  Let the input to~$A$ be the triple $(a, b, \end{slide} \begin{proof} Suppose that$A$solves the oracle hash decision problem for$\Xid{\mathcal{K}}{DH}^{G, H}$. Let the input to~$A$be the triple$(a, b,
-  h)$, where$a = g^\alpha$,$b = g^\beta$and$h$is some string in$\{0,
-  1\}^k$; and let$h^* = H(g^\beta, g^{\alpha\beta})$.$A$must decide - whether$h = h^*$. Clearly, if$A$never queries$H$at$(g^\beta,
-  g^{\alpha\beta})$then its advantage is zero, since it has no information - about$h^*$. + h^*)$, where $a = g^\alpha$ and $b = g^\beta$; and let $h^* = + H(g^{\alpha\beta})$.  $A$ must decide whether $h = h^*$.  Clearly, if $A$
+  never queries $H$ at $(g^\beta, g^{\alpha\beta})$ then its advantage is
+  zero, since it has no information about $h^*$.

As in the one-way function case, we have
$\Pr[F] \ge \frac{1}{2} \Adv{ohd}{\Xid{\mathcal{K}}{DH}^{G, H}}(A)$

As in the one-way function case, we have
$\Pr[F] \ge \frac{1}{2} \Adv{ohd}{\Xid{\mathcal{K}}{DH}^{G, H}}(A)$
@@ -258,7 +257,7 @@ in \cite{Abdalla:2001:DHIES}.
\begin{program}
Algorithm $B^{C(\cdot, \cdot)}(a^*, b^*)$: \+ \\
$\Xid{R}{map} \gets \emptyset$; $\Xid{H}{map} \gets \emptyset$; \\
\begin{program}
Algorithm $B^{C(\cdot, \cdot)}(a^*, b^*)$: \+ \\
$\Xid{R}{map} \gets \emptyset$; $\Xid{H}{map} \gets \emptyset$; \\
-      $h^* \getsr \{0, 1\}^k$; \\
+      $h^* \gets \{0, 1\}^k$; \\
$c^* \gets \bot$; \\
$b \gets A^{\Xid{R}{sim}(\cdot), \Xid{H}{sim}(\cdot)} (a^*, b^*, h^*)$; \\
$c^* \gets \bot$; \\
$b \gets A^{\Xid{R}{sim}(\cdot), \Xid{H}{sim}(\cdot)} (a^*, b^*, h^*)$; \\
@@ -266,7 +265,7 @@ in \cite{Abdalla:2001:DHIES}.
Oracle $\Xid{R}{sim}(b)$: \+ \\
\IF $b \in \dom\Xid{R}{map}$ \\
\THEN \RETURN $\Xid{R}{map}(b)$; \\
Oracle $\Xid{R}{sim}(b)$: \+ \\
\IF $b \in \dom\Xid{R}{map}$ \\
\THEN \RETURN $\Xid{R}{map}(b)$; \\
-      $h \getsr \{0, 1\}^k$; \\
+      $h \gets \{0, 1\}^k$; \\
$\Xid{R}{map} \gets \Xid{R}{map} \cup \{ b \mapsto h \}$; \\
\RETURN $h$;
\next
$\Xid{R}{map} \gets \Xid{R}{map} \cup \{ b \mapsto h \}$; \\
\RETURN $h$;
\next
@@ -275,7 +274,7 @@ in \cite{Abdalla:2001:DHIES}.
\IF $(b, c) \in \dom\Xid{H}{map}$ \THEN
\RETURN $\Xid{H}{map}(b, c)$; \\
$h \gets \{0, 1\}^k$; \\
\IF $(b, c) \in \dom\Xid{H}{map}$ \THEN
\RETURN $\Xid{H}{map}(b, c)$; \\
$h \gets \{0, 1\}^k$; \\
-        $\Xid{H}{map} \getsr \Xid{H}{map} \cup \{ (b, c) \mapsto h \}$; \\
+        $\Xid{H}{map} \gets \Xid{H}{map} \cup \{ (b, c) \mapsto h \}$; \\
\RETURN $h$; \- \\
\IF $b = b^*$ \THEN \\ \quad \= \+ \kill
$c^* \gets c$; \\
\RETURN $h$; \- \\
\IF $b = b^*$ \THEN \\ \quad \= \+ \kill
$c^* \gets c$; \\