DLOG ⊆ TFNP

Inclusion · folklore

Statement

When the group order is known and membership $h\in ⟨g⟩$ is checkable in polynomial time (for prime order $p$: $g\ne 1$ and $h^p=1$), the DLOG search problem of finding $x$ with $g^x=h$ given $(\mathbb{G},g,p,h)$ is in TFNP — folklore.

Sketch

Every $h\in ⟨g⟩$ has a discrete logarithm $x\in {\mathbb{Z}}_p$, and a candidate $x$ is checked with one exponentiation; on an input that fails the membership test, the verifier accepts a fixed dummy solution.

Notes

• Suitable formulations of discrete logarithm over general groups are complete for PPP and PWPP, the pigeonhole subclasses of TFNP, answering an open question of SZZ18 — HV21.