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 — TODO citation

Vairations

One-more Discrete Logarithm

In some works (TODO-cite), it is important to consider adversaires

\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.