\section{El Gamal}
This scheme was invented by ElGamal \cite{El85}.  It's
security is based on the DH and DL problems.
\algo{ElGamal key generation}{
\step{Pick a large random prime $p$.}
\step{Pick a generator $\alpha$ of $\bbZ^{*}_p$ and a random
integer $a$, $1 \leq a \leq p - 2$.}
\step{$\beta \leftarrow \alpha^a \; mod \; p$.}
\step{{\bf RETURN} $K_e = (p, \alpha, \beta)$ and $K_d = a$.}
}

\algo{ElGamal public-key encryption}{
\step{Pick a random integer $k$, $1 \leq k \leq p -2$.}
\step{$\gamma \leftarrow \alpha^k \; mod \; p$, 
      $\delta \leftarrow m \cdot \beta^k \; mod \; p$.}
\step{{\bf RETURN}$c = (\gamma, \delta)$.}
}
{\bf Decryption:} $m \leftarrow \delta(\gamma)^{-1} \; mod \; p$.\\
{\it Proof that} $d(e(x)) = x$:\\
\begin{eqnarray*}
  d(\gamma, \delta) & = & \delta \cdot (\gamma^a)^{-1} \; mod \; p \\
                    & = & m \cdot \beta^k((\alpha^k)^a)^{-1} \; mod \; p \\
                    & = & m \cdot \beta^k(\beta)^{-1} \; mod \; p \\
                    & = & m \; mod \; p.
\end{eqnarray*}
\begin{theorem} Different random integers $k$ must be used if not 
information about the cleartexts are revealed.
\end{theorem}
\begin{proof}
Say we have 
\begin{eqnarray*}
    e(m_1, k) & = & (\alpha^k \; mod \; p, \underbrace{m_1 \cdot \beta^k \; mod \; p}_{\delta_1}) \; and \\
    e(m_2, k) & = & (\alpha^k \; mod \; p, \underbrace{m_2 \cdot \beta^k \; mod \; p}_{\delta_2})
\end{eqnarray*}
we can then compute $\delta_1 / \delta_2 = m_1 / m_2 \; mod \; p$.
\end{proof}

\begin{theorem}The security of the ElGamal System is based on the
DH problem.
\end{theorem}
\begin{proof}
Denote $O_{ElGamal}$ to be an oracle for decrypting ElGamal encrypted messages, 
given $p, \alpha, \alpha^a, \alpha^k, m \cdot \alpha^{ak}$ and $O_{DH}$
an oracle
for solving the DH (that is $DH(p, \alpha, \alpha^a, \alpha^b)$ gives
$\alpha^{ab}$).\\
\begin{itemize}
  \item($O_{ElGamal}$ from $O_{DH}$)  Compute $\alpha^{ak}$ using $O_{DH}$.
      We then have $m \leftarrow (\alpha^{ak})^{-1} \cdot \delta$. \\
  \item($O_{DH}$ from $O_{ElGamal}$)  Pick a random $c \in \bbZ_p$.
      Compute $O_{ElGamal}(p, \alpha, \alpha^a, \alpha^b, r)$, which
      gives $m$ such that $m\cdot \alpha^{ab} = r$.  We have
      $\alpha^{ab} \leftarrow r \cdot m^{-1}$.
\end{itemize}
\end{proof}

\subsection{Generalizing ElGamal}
We described the ElGamal system in a group $\bbZ^{*}_p$, but it can be
generalized to work in any finite cyclic group $G$.  It's security is
then {\it based} on the DL problem of that particular group.  Examples
of groups in which the DL problem is beleived to be hard and in which
operations can be efficiently executed are 
$$\bbZ^{*}_p, \GF{2^m}^{*}, \GF{q^m}^{*}, \bbZ^{*}_{pq}$$.

\begin{theorem}
In the case of $\bbZ^{*}_N$ where $N = pq$ and $p \equiv q \equiv 3 \; (mod \; 4)$,
the DL problem is polynomialy equivalent to FACTORING.
\end{theorem}
Note: for the case of $\bbZ^{*}_N$ where $N = pq$, it is recommended to pick $p$ and
$q$ in such a way that $p-1$ and $q-1$ do not have small factors, so as to guard
against {\it Pollard's} factoring algorithm.
