DDH ⇒ CDH

Fully-black-box reduction · standard model · folklore · security loss: tight up to an additive $1/p$: one CDH call

Statement

If DDH is hard for a group generator $\mathsf{GrGen}$, then CDH is hard for $\mathsf{GrGen}$: for every CDH adversary $\mathcal{A}$ there is a DDH adversary $\mathcal{B}$, making one call to $\mathcal{A}$, with ${\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{B}}^{\text{ddh}}(\lambda )\ge {\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{A}}^{\text{cdh}}(\lambda )-1/p$, $p$ the group order — folklore.

Sketch

On a DDH challenge $(g,g^x,g^y,Z)$, run the CDH adversary on $(g^x,g^y)$ and guess the real world iff it returns $Z$. A real tuple is recognised with the adversary’s success probability; for a random tuple $Z$ is uniform and independent of the adversary’s output, so it matches with probability $1/p$.