Discrete logarithm

The discrete logarithm (DLOG) assumption is used throughout cryptography. It is implied by the CDH assumption: an adversary which can solve the DLOG problem can also solve CDH in the same group — folklore.

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

• CDH ⇒ DLOG
• GGM ⇒ DLOG
• In the Generic Group Model, for groups of prime order $p$, ${\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 — Sho97

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$. Its running time $O(\sqrt{p})$, attained at $S=O(\sqrt{p})$, is optimal in the GGM for groups of prime order $p$: every generic algorithm needs $\Omega (\sqrt{p})$ group operations — Sho97
• 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}]$.
• Quantum: Shor’s algorithm computes discrete logarithms in ${\mathbb{Z}}_p^{\ast }$ in quantum polynomial time — Shor97; it extends to any group with efficient group operations on unique encodings, elliptic-curve groups included — BL95. See DLOG ⊆ BQP.

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.

Participates in

Builds on Discrete logarithm

• DLOG ⇒ Schnorr signatures
• DLOG ⇒ BLS signatures
• DLOG ⊆ BQP
• DLOG ⇒ CDH
• DLOG ⇒ Statistically hiding commitment
• DLOG ⊆ coNP
• DLOG ⊆ NP
• DLOG ⇒ PCS
• DLOG ⇒ PRG
• DLOG ⇒ Schnorr identification protocol
• DLOG ⊆ TFNP
• DLOG ⇒ Verifiable secret sharing (VSS)

Produces Discrete logarithm

• CDH ⇒ DLOG
• GGM ⇒ DLOG
• Structured GGM ⇒ DLOG