GGM ⇒ DDH

Free reduction · generic group model · Sho97 · security loss: advantage $O(q^2/p)$ for $q$ queries, $p$ the prime group order

Statement

In the generic group model, DDH is hard in groups of prime order $p$: every generic distinguisher $\mathcal{A}$ between $(g,g^x,g^y,g^{xy})$ and $(g,g^x,g^y,g^z)$ making $q$ group-operation queries has ${\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{A}}^{\text{ddh}}(\lambda )=O(q^2/p)$, so deciding DDH generically takes $\Omega (\sqrt{p})$ queries — Sho97.

Sketch

Treat $x,y,z$ as indeterminates, answer group-oracle queries with random labels, and record the affine polynomial each label represents; in the real world substitute $z=xy$, giving polynomials of degree at most $2$. Choosing the point only after the adversary halts, the two worlds are simulated identically unless two distinct recorded polynomials agree at it, probability at most $2/p$ per pair over $O(q^2)$ pairs.

Notes

• Prime order and genericity are both needed: a small prime factor of the group order gives a generic distinguisher (project onto the small subgroup), and a symmetric pairing, which is not a generic operation, decides DDH outright — standard; see DDH attacks.