BDH ⇒ CDH

Fully-black-box reduction · standard model · BF01 · security loss: tight: one CDH call and one pairing evaluation

Statement

If BDH is hard for a symmetric pairing-group generator, then CDH is hard in its source group $\mathbb{G}$: every CDH solver yields, with one call and one pairing evaluation, a BDH solver with at least its success probability — BF01.

Sketch

Given a BDH instance $(g,g^a,g^b,g^c)$, run the CDH solver on $(g,g^a,g^b)$ and output $e(Z,g^c)$ for its answer $Z$. This equals $e(g,g{)}^{abc}$ whenever $Z=g^{ab}$, and $(g^a,g^b)$ is distributed as in the CDH game.

Notes

• The converse, that CDH hardness implies BDH hardness, is open — BF01.