No fixed-construction reduction from CDH to DDH

Conditional · against fixed-construction reductions · assuming Bilinear map assumptions · JN03, BF01

Statement

The identity map on group generators is no reduction from CDH to DDH unless BDH fails for every symmetric-pairing group generator. In a group $\mathbb{G}$ with an efficient symmetric pairing $e:\mathbb{G}\times \mathbb{G}\to {\mathbb{G}}_T$, such as a suitable supersingular elliptic curve, DDH is decided by checking $e(g^x,g^y)=e(g,g^z)$, and JN03 exhibit such groups in which CDH is equivalent to a presumably hard discrete logarithm problem — JN03. BDH hardness for a symmetric-pairing generator implies CDH hardness in its source group (BDH ⇒ CDH) — BF01, so such a generator has hard CDH and easy DDH.

Sketch

Given $(g,g^x,g^y,Z)$, guess the real tuple iff $e(g^x,g^y)=e(Z,g)$. Bilinearity gives $e(g^x,g^y)=e(g,g{)}^{xy}$ and $e(Z,g)=e(g,g{)}^z$ for $Z=g^z$, and non-degeneracy makes $e(g,g)$ a generator of ${\mathbb{G}}_T$, so the test accepts iff $z=xy$: advantage $1-1/p$ — standard.

Notes

• The converse holds for every group generator: DDH ⇒ CDH — folklore.