DLOG ⇒ CDH

Algebraic group model · FKL18 · security loss: tight: same advantage and essentially the same running time (FKL18)

Statement

In the algebraic group model, CDH is as hard as DLOG: for every prime-order group generator $\mathsf{GrGen}$ and every algebraic CDH adversary $\mathcal{A}$ there is a DLOG adversary $\mathcal{B}$ with ${\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{B}}^{\text{dl}}(\lambda )\ge {\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{A}}^{\text{cdh}}(\lambda )$ and essentially the running time of $\mathcal{A}$ — FKL18.

Sketch

The reduction rerandomizes a DLOG challenge $Z=g^z$ into a CDH instance $(X,Y)$ whose exponents are known affine functions of $z$. The adversary’s answer comes with coefficients expressing it as a product of powers of $g$, $X$ and $Y$, so a correct answer gives a quadratic equation in $z$ over ${\mathbb{Z}}_p$ with nonzero leading coefficient, whose at most two roots the reduction computes and checks against $Z$.

Notes

• The converse, CDH ⇒ DLOG, holds in the standard model, so CDH and DLOG are equivalent against algebraic adversaries — FKL18.