Discrete logarithm

The discrete logarithm (DLOG) assumption is used throughout cryptography. It is a natural strengthening of the CDH assumption. In other words, an adversary which can solve the DLOG problem can also solve CDH in the same group.

Assumption

Informally, the DLOG assumption concerns a cyclic group generation algorithm $\mathsf{GrGen},$ which takes as input a security parameter $1^{\lambda }$ and outputs a succinct description of a cyclic group $(\mathbb{G},g,p),$ where $\mathbb{G}$ is the group set, $g$ is a generator for the group, and $p$ is the order of the group.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\text{dl}}_{\GrGen,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\GG,g,p) \gets \GrGen(1^\secpar)$
\State $x \getsr [p]$
\State $X \gets g^x$
\State $\hat{x} \gets \calA(1^\secpar, \GG, g, p, X)$
\Return $[\hat{x} = x]$
\end{algorithmic}
\end{algorithm}

We say that DLOG is hard for a group generation algorithm $\mathsf{GrGen}$ if for all efficient $\mathcal{A},$

$${\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{A}}^{\text{dl}}(\lambda ):=\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{GrGen},\mathcal{A}}^{\text{dl}}(\lambda )=1\right]$$

is negligible.

Related results

• It is easy to see that if $\mathcal{A}$ can compute $x$ for a random $g^x$, then $\mathcal{A}$ can compute both $x$ and $y$ from $g^x$ and $g^y$ and find $g^{xy}$ easily. This establishes that DLOG is not easier than CDH.
• In the Generic Group Model, ${\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{A}}^{\text{dl}}(\lambda )\le O(\frac{q^2}{p})$, where $q$ is the number of queries that $\mathcal{A}$ issues — Shoup97

Attacks

• The Baby-step Giant-step is a generic attack which works in all groups and requires space $S$ and time $T$ with $S\cdot T\ge p$. Therefore, this is optimal in the GGM — Shoup97
• Index calculus: sub-exponential attack on DLOG in ${\mathbb{F}}_p^{\ast }$ (multiplicative group of a finite field) and in the Jacobians of hyperelliptic curves of high genus. Does not apply to generic elliptic curve groups, which is why ECDLP is believed harder than DLOG in ${\mathbb{F}}_p^{\ast }$.
• Pohlig-Hellman: reduces DLOG in a group of composite order $n=\prod p_i^{e_i}$ to DLOG in groups of prime order $p_i$ via the Chinese Remainder Theorem. Effective when $n$ is smooth; neutralized by using prime-order groups.
• Number Field Sieve (NFS): sub-exponential algorithm for DLOG in ${\mathbb{F}}_p^{\ast }$; best known algorithm with complexity $L_p[1/3,(64/9{)}^{1/3}]$.

Variations

One-more Discrete Logarithm

In some works, it is important to consider adversaries

\begin{algorithm}
% oracle-split: 40
\algname{Game}
\caption{$\Game^{\text{om-dl}}_{\GrGen,\calA, \ell}(\secpar)$}
\begin{algorithmic}
\State $(\GG,g,p) \gets \GrGen(1^\secpar)$ ; $q \gets 0$
\For{$i = 1,\ldots,\ell+1$}
\State $x_i \getsr [p]$
\State $X_i \gets g^{x_i}$
\EndFor
\State $(\hat{x}_i)_{i\in [\ell+1]} \gets \calA^{\calO_{\text{dl}}}(1^\secpar, \GG, g, p, (X_i)_{i\in [\ell+1]})$
\Return $\big[q \le \ell \land \forall_{i\in [\ell+1]}~~x_i = \hat{x}_i\big]$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Oracle}
\caption{$\calO_{\text{dl}}(Z)$}
\begin{algorithmic}
\State $q \gets q + 1$
\State $z \gets \mathrm{dlog}_g(Z)$
\Return $z$
\end{algorithmic}
\end{algorithm}

We say that OM-DL is hard for a group generation algorithm $\mathsf{GrGen}$ if for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{A}}^{\text{om-dl}}(\lambda ):=\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{GrGen},\mathcal{A}}^{\text{om-dl}}(\lambda )=1\right]$$

is negligible.