## -*-fundamental-*-
##
-## $Id$
+## $Id: Makefile.m4,v 1.1 2002/02/24 15:43:20 mdw Exp $
##
## Makefile for IPS
##
## along with this program; if not, write to the Free Software Foundation,
## Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
-##----- Revision history ----------------------------------------------------
-##
-## $Log: Makefile.m4,v $
-## Revision 1.1 2002/02/24 15:43:20 mdw
-## New build system.
-##
-
AUTOMAKE_OPTIONS = foreign
SRC = \
dnl -*-fundamental-*-
dnl
-dnl $Id$
+dnl $Id: configure.in,v 1.2 2002/07/17 08:52:06 mdw Exp $
dnl
dnl Dummy configuration script for ips
dnl
dnl along with this program; if not, write to the Free Software Foundation,
dnl Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
-dnl ----- Revision history --------------------------------------------------
-dnl
-dnl $Log: configure.in,v $
-dnl Revision 1.2 2002/07/17 08:52:06 mdw
-dnl Various small fixes.
-dnl
-dnl Revision 1.1 2002/02/24 15:43:20 mdw
-dnl New build system.
-dnl
-
AC_INIT(ips.tex)
AM_INIT_AUTOMAKE(ips, 1.1.1)
AC_OUTPUT(Makefile)
\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
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,
- 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) \]
\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^*)$; \\
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
\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$; \\