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). It extends to the Jacobians of hyperelliptic curves of high genus — ADH94. 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 — PH78.
• Number Field Sieve (NFS): sub-exponential algorithm for DLOG in ${\mathbb{F}}_p^{\ast }$, heuristically running in time $L_p[1/3,3^{2/3}]$ — Gor93.
• 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

DLOG in prime-order groups

DLOG is hard in prime-order groups for $\mathsf{GrGen}$ if every group $\mathsf{GrGen}$ outputs has prime order $p$ and DLOG is hard for $\mathsf{GrGen}$. Exponents then form the field ${\mathbb{Z}}_p$, so a construction may divide by any nonzero exponent.

DLOG in compactly encoded prime-order groups

DLOG is hard in compactly encoded prime-order groups for $\mathsf{GrGen}$ if DLOG is hard in prime-order groups for $\mathsf{GrGen}$ and every group $(\mathbb{G},g,p)$ it outputs encodes its elements in fewer than $2\lfloor \log p\rfloor$ bits. The order-$p$ subgroup of ${\mathbb{Z}}_P^{\ast }$ for a safe prime $P=2p+1$ and prime-order elliptic-curve groups with compressed points (an $x$-coordinate and one bit) meet the bound; uncompressed affine points, and the order-$p$ subgroup of ${\mathbb{Z}}_P^{\ast }$ with $\log P\ge 2\log p$, do not — standard.

DLOG in prime-order subgroups of twisted Edwards curves

DLOG is hard in prime-order subgroups of twisted Edwards curves for $\mathsf{GrGen}$ if DLOG is hard in prime-order groups for $\mathsf{GrGen}$ and every group $(\mathbb{G},g,p)$ it outputs is the subgroup of prime order $p$ generated by a point $g$ of a twisted Edwards curve over a finite field. These are the groups EdDSA works in.

$q$-DLOG

The assumption concerns a bilinear group generator $\mathsf{GrGen}$, which on input $1^{\lambda }$ outputs $({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_T,p,g_1,g_2,e)$: cyclic groups of prime order $p$ with ${\mathbb{G}}_1\ne {\mathbb{G}}_2$ (an asymmetric pairing), generators $g_1$ of ${\mathbb{G}}_1$ and $g_2$ of ${\mathbb{G}}_2$, and a non-degenerate bilinear pairing $e:{\mathbb{G}}_1\times {\mathbb{G}}_2\to {\mathbb{G}}_T$. Let $q_1=q_1(\lambda )$ and $q_2=q_2(\lambda )$ be polynomials.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{(q_1,q_2)\text{-dl}}_{\GrGen,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\GG_1, \GG_2, \GG_T, p, g_1, g_2, e) \gets \GrGen(1^\secpar)$
\State $x \getsr \ZZ_p$
\State $\hat{x} \gets \calA(1^\secpar, \GG_1, \GG_2, \GG_T, p, g_1, g_2, e, (g_1^{x^i})_{i=1}^{q_1}, (g_2^{x^i})_{i=1}^{q_2})$
\Return $[\hat{x} = x]$
\end{algorithmic}
\end{algorithm}

$(q_1,q_2)$-DLOG is hard for $\mathsf{GrGen}$ if for all efficient $\mathcal{A}$,

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

is negligible — FKL18. $q$-DLOG is hard for $\mathsf{GrGen}$ if $(q_1,q_2)$-DLOG is hard for every pair of polynomials $q_1,q_2$. Dropping powers turns an instance for $(q_1,q_2)$ into one for any smaller pair, so larger degrees give the stronger assumption, and $q$-DLOG implies DLOG in the prime-order group ${\mathbb{G}}_1$ (q-DLOG ⇒ Prime-order DLOG) — folklore. In the algebraic group model, knowledge soundness of Groth’s SNARK reduces to it — FKL18.

One-more Discrete Logarithm

In the one-more discrete logarithm (OMDL) problem, the adversary gets $\ell +1$ challenges $X_i=g^{x_i}$ and an oracle returning ${\log }_{g}Z$ for any $Z\in \mathbb{G}$ it submits; it must output every $x_i$ after at most $\ell$ oracle queries. One-more problems go back to the one-more RSA-inversion problems of BNPS03; BP02 use OMDL to prove the Schnorr identification protocol secure under concurrent attack.

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

OMDL is hard for a group generation algorithm $\mathsf{GrGen}$ if every group $(\mathbb{G},g,p)$ that $\mathsf{GrGen}$ outputs has prime order $p$ and, for every polynomial $\ell =\ell (\lambda )$ and all efficient $\mathcal{A}$,

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

is negligible.

• With $\ell =0$ the game is the DLOG game, so OMDL implies DLOG in prime-order groups (OMDL ⇒ Prime-order DLOG) — folklore.
• Since $\ell$ ranges over all polynomials, no polynomial bounds the number of rounds of the game in advance. No Turing reduction bases OMDL on an assumption with an a priori bounded number of rounds unless that assumption is false (barrier) — Pas11.
• OMDL holds in the generic group model (GGM ⇒ OMDL) — BFP21.

Participates in

Builds on Discrete logarithm

• Bilinear pairing + q-DLOG ⇒ Universal SNARK (PLONK) (via $q$-DLOG)
• Bilinear pairing + q-DLOG ⇒ zk-SNARK (Groth16 in the AGM) (via $q$-DLOG)
• Compactly encoded prime-order DLOG ⇒ Prime-order DLOG (via DLOG in compactly encoded prime-order groups)
• DLOG ⇒ Schnorr signatures (via DLOG in prime-order groups)
• DLOG ⇒ BLS signatures
• DLOG ⊆ BQP
• DLOG ⇒ CDH
• DLOG ⇒ Statistically hiding commitment (via DLOG in prime-order groups)
• DLOG ⊆ coNP
• DLOG ⇒ CRHF (via DLOG in compactly encoded prime-order groups)
• DLOG ⊆ NP
• DLOG ⇒ PCS
• DLOG ⇒ PRG
• DLOG ∈ PWPP
• DLOG ⇒ Schnorr identification protocol (via DLOG in prime-order groups)
• DLOG ∈ SZK
• DLOG ⊆ TFNP
• DLOG ⇒ Verifiable secret sharing (VSS)
• OMDL + ROS ⇒ Blind Schnorr signatures (via One-more Discrete Logarithm)
• OMDL ⇒ Schnorr identification under concurrent attack (via One-more Discrete Logarithm)
• OMDL ⇒ MuSig2 (via One-more Discrete Logarithm)
• OMDL ⇒ Prime-order DLOG (via One-more Discrete Logarithm)
• DLOG ⇒ Blind Okamoto–Schnorr signatures (via DLOG in prime-order groups)
• Prime-order DLOG ⇒ DLOG (via DLOG in prime-order groups)
• DLOG ⇒ EdDSA (via DLOG in prime-order subgroups of twisted Edwards curves)
• DLOG ⇒ Succinct arguments for NP (Bootle et al.) (via DLOG in prime-order groups)
• DLOG ⇒ MuSig (via DLOG in prime-order groups)
• DLOG ⇒ Okamoto identification protocol (via DLOG in prime-order groups)
• DLOG ⇒ Schnorr signatures (tight, AGM) (via DLOG in prime-order groups)
• q-DLOG ⇒ Prime-order DLOG (via $q$-DLOG)
• Twisted Edwards DLOG ⇒ Prime-order DLOG (via DLOG in prime-order subgroups of twisted Edwards curves)

Produces Discrete logarithm

• CDH ⇒ DLOG
• Compactly encoded prime-order DLOG ⇒ Prime-order DLOG (via DLOG in prime-order groups)
• GGM ⇒ DLOG
• GGM ⇒ OMDL (via One-more Discrete Logarithm)
• GGM with preprocessing ⇒ DLOG
• OMDL ⇒ Prime-order DLOG (via DLOG in prime-order groups)
• Prime-order DLOG ⇒ DLOG
• q-DLOG ⇒ Prime-order DLOG (via DLOG in prime-order groups)
• Structured GGM ⇒ DLOG
• Twisted Edwards DLOG ⇒ Prime-order DLOG (via DLOG in prime-order groups)

Barriers

• No fully-black-box reduction from bounded-round assumptions to OMDL (via One-more Discrete Logarithm)
• No algebraic reduction from OMDL to two-round MuSig (via One-more Discrete Logarithm)
• No single-instance reduction from DLOG to Schnorr signatures in the non-programmable ROM (via DLOG in prime-order groups) — circumvented by DLOG ⇒ Schnorr signatures, DLOG ⇒ Schnorr signatures (tight, AGM)
• No tight generic reduction from DLOG to Schnorr signatures (via DLOG in prime-order groups) — circumvented by DLOG ⇒ Schnorr signatures, DLOG ⇒ Schnorr signatures (tight, AGM)
• No algebraic reduction from DLOG to Schnorr signatures in the standard model (via DLOG in prime-order groups) — circumvented by DLOG ⇒ Schnorr signatures, DLOG ⇒ Schnorr signatures (tight, AGM)
• No tight algebraic reduction from DLOG to Schnorr signatures in the ROM (via DLOG in prime-order groups) — circumvented by DLOG ⇒ Schnorr signatures, DLOG ⇒ Schnorr signatures (tight, AGM)