
\section{Discrete Logarithm Problems and the Diffie-Hellman Key Exchange}

\subsection{Discret Logarithm Problems}
\begin{definition}(Generalized Discret Logarithm Problem (GDLP))
Gievn a group $G$ of order $n$, $\alpha$ a generator of $G$ and 
$\beta \in G$, find $e$ such that $\alpha^e \equiv \beta$, $0 \leq e
\leq
n-1$.
\end{definition}

\begin{definition}(Discret Logarithm Problem (DLP))
  DLP is GDLP but in a group of order $p$ where $p$ is prime.
\end{definition}

An even greater generalization is to consider GDLP but with $G$ not 
necessarily cyclic ($\alpha$ not necessarily a generator) and to
find $e$ if such an integer exists.  This problem is considered to 
be harder than GDLP.

\vspace{0.6cm}
We now discuss the most important known algorithms for the DLP.

\subsection{Big-Step giant-step algorithm}
This algorithm has been credited to D. Shanks (\cite{Kn73}).  It is
a time-memory trade-off method. \\
Consider $\alpha, \; \beta \in G$ (an arbitrary group). 
Let $m = \ceiling{\sqrt{n}}$, where $n$ is the order of $\alpha$.
We want to compute $x$ such that $\beta = \alpha^x$. The algorithm
is based on the fact that we can write $x = im + j$, where 
$0 \leq i,\; j \le m$, and thus $\alpha^x = \alpha^{im}\alpha^j$,
which implies $\beta(\alpha^{-m})^i = \alpha^j$.  The algorithm
precomputes and stores
the pairs $(j, \alpha^j)$, $0 \leq j \le m$ in order in a table, and 
then loops on 
$i = 0$, to $m-1$, verifying if $\alpha^{-mi}$ is in the table.

\algo{Baby-step giant-step algo for DLP}{
\label{babyshank}
\step{ $m \leftarrow \ceiling{\sqrt{n}}$.}
\step{ Construct a table with the pairs $(\alpha^j, j)$, $0 \leq j \le m$,
       ordered by the first elements of each pair.}
\step{ $\gamma \leftarrow \beta$ }
\step{ {\bf FOR} $i = 0$ {\bf TO} $m - 1$ {\bf DO} }
\step{ \hspace{0.6cm} Verify if $(\gamma, j)$ is in the table for some $j$.}
\step{ \hspace{0.6cm} {\bf IF} $\gamma = \alpha^j$ {\bf THEN RETURN} 
       $x = i \cdot m + j$ }
\step{ \hspace{0.6cm} $\gamma \leftarrow \gamma \cdot \alpha^{-m}$ }
}
The algorithm uses $O(\sqrt{n})$ memory.
The precomputation stage (step 1 and 2) takes $O(\sqrt{n})$ group
multiplications and $O(\lg n \; \sqrt{n})$ comparisons to sort
(note: a thought to be valid assumption is that a group
multiplication takes longer then $lg \; n$ comparisons).  The searching
in the table takes $O(\sqrt{n})$ group multiplication.  

\subsection{Pohlig-Hellman algorithm for DLP}

This algorithm (\cite{PH78}) reduces the DLP in $G$ to the same problem in
the minimal
non-trivial subgroups of $G$.  It uses the prime factorization of the
order $n$
of the group $G$. 
Let ${p_1}^{e_1} {p_2}^{e_2} \ldots {p_r}^{e_r} = n$ be the prime
factorization
of $n$. To solve $x$ such that $\alpha^x = \beta$ in $G$, determine
$x_i = x \; mod \; {p_i}^{e_i}$, for $1 \leq i \leq t$, then use the
chinese
remainder theorem (\ref{chinese}) to compute $x$.  To compute
$x_i = x \; mod \; {p_i}^{e_i}$, we determine, modulo $q_i$, the
coefficients
$l_j$ of the $q_i$-adic representation of $x$ modulo ${q_i}^{e_i}$:
$$x = \sum_{j=0}^{e_i -1} l_j \cdot {q_i}^j \; mod \; {q_i}^{e_i}$$.

\algo{pohlig-hellman algorithm for DLP}{
\step{ $n \leftarrow {p_1}^{e_1} {p_2}^{e_2} \ldots {p_r}^{e_r}$, 
        where $e_i \geq 1.$ }
\step{ {\bf FOR} $i = 1$ {\bf TO} $r$ {\bf DO} }
\step{ \hspace{0.6cm} $\gamma =1$, $\l_{-1} \leftarrow 0.$ }
\step{ \hspace{0.6cm} $\overline{\alpha}  \leftarrow \alpha^{n/q}$. }
\step{ \hspace{0.6cm} {\bf FOR} $j = 0$ {\bf TO} $e-1$ {\bf DO} }
\step{ \hspace{1.2cm} $\gamma \leftarrow \gamma\alpha^{l_{j-1}q^{j-1}}$,
          $\overline{\beta} \leftarrow (\beta\gamma^{-1})^{n/q^{j+1}}$. }
\step{ \hspace{1.2cm} 
          $l_j \leftarrow \; log_{\overline{\alpha}}\overline{\beta}$
          using \ref{shankbaby}. }
\step{ \hspace{0.6cm} $x_i \leftarrow l_0 + l_iq + \ldots
l_{e-1}q^{e-1}$.}
\step{ Use \ref{chinese} to compute $x$. }
\step{ {\bf RETURN} $x$ }.
}

To convince yourself that the algorithm is correct, observe that 
in step 4 the order of $\overline{\alpha}$ is $q$ and that at iteration
$j$ of step 6 we have 
    $\gamma = \alpha^{l_0 + l_1q + \ldots + l_{j-1}q^{j-1} }.$
Then note that
\begin{eqnarray*}
\overline{\beta} &=& (\beta\gamma^{-1})^{n/q^{j+1}}  \\
   &=& (\alpha^{x-l_0-l_1q-\ldots -l_{j-1}q^{j-1}})^{n/q^{j+1}} \\
   &=& (\alpha^{n/q^{j+1}})^{x_i-l_0-l_1q-\ldots -l_{j-1}q^{j-1}} \\
   &=& (\alpha^{n/q^{j+1}})^{l_jq^j + \ldots + l_{e-1}q^{e-1}} \\
   &=& (\alpha^{n/q})^ {l_j + \ldots + l_{e-1}q^{e-1-j}}  \\
   &=& \overline{\alpha}^{l_j} 
\end{eqnarray*}

\subsection{Diffie-Hellman key exchange}

In a landmark paper \cite{DH76}, W. Diffie and M.E. Hellman introduced
an algorithm for exchanging a symmetric key in public.  They also 
proposed the existence of public symmetric encryption, authentification
and digital signature schemes.  In the Diffie-Hellman key exchange
scheme, $Alice$ and $Bob$ both share a large public prime $p$ and a
primitive element $g$ of $\bbZ_p$.  $Alice$, (and independantly $Bob$)
picks a random integer $x \in_R \bbZ_p$ ($Bob$ picks $y \in_R \bbZ_p$)
and computes $u = g^x \; mod \; p$ ($Bob$ computes $v = g^y \; mod \; p$).
$Alice$ then sends $u$ to $Bob$, via a public chanel, and $Bob$ sends
his value $v$to $Alice$.  $Alice$s private key is computed as 
$K_{Alice} = v^x \; mod \; p$ ($K_{Bob} = u^x \; mod \; p$). \\
We easily see that $K_{Alice} = K_{Bob}$, this is their symmetric 
key.\\

\subsubsection{Cryptanalysis:  Diffie-Hellman problem}
  $Oscar$s job is to try to compute $K$ given $g$, $p$, $u$ and $v$, wich
gives rise to the following problem
\begin{definition}(Diffie-Hellman Problem DHP)
Given a prime $p$, a generator $\alpha \in \bbZ_p$, $\alpha^x \; mod \;p$
and $\alpha^y \; mod \; p$, find $\alpha^{xy}$.
\end{definition}
Diffie-Hellman assumption:  no efficient algorithm can solve the above
problem.\\
This assumption is at least as strong as the DLP (DHP $\leq_P$ DLP), for
if $Oscar$ could easily compute $x$ and $y$ from $\alpha^x$ and 
$\alpha^y$, he can then easily compute $K = (\alpha^x)^y$.
The Generalized DHP (GDHP) is like DHP but working on a finite cyclic
group $G$ (instead of just ${\bbZ_p}^*$).\\
GDHP is also at least as strong as GDLP.  It is still unknown if
GDLP is as strong as GDHP, however some equivalence (for some specific
classes of groups) are known (see \cite{Bo88} and \cite{Ma94}).


