CDH ⇒ DLOG

Fully-black-box reduction · standard model · folklore · security loss: tight: one DLOG call, advantage-preserving

Statement

If CDH is hard for a group generator $\mathsf{GrGen}$, then DLOG is hard for $\mathsf{GrGen}$: for every DLOG adversary $\mathcal{A}$ there is a CDH adversary $\mathcal{B}$, making one call to $\mathcal{A}$ and one exponentiation, with ${\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{B}}^{\text{cdh}}(\lambda )\ge {\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{A}}^{\text{dl}}(\lambda )$ — folklore.

Sketch

Given a CDH instance $(g,g^x,g^y)$, run the DLOG solver on $(g,g^x)$ and output $(g^y{)}^{\hat{x}}$ for its answer $\hat{x}$. Since $g^x$ is distributed as in the DLOG game, the reduction succeeds whenever the solver does.