GGM ⇒ CDH

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

Statement

In the generic group model, CDH is hard in groups of prime order $p$: every generic algorithm $\mathcal{A}$ making $q$ group-operation queries computes $g^{xy}$ from $(g,g^x,g^y)$ with probability ${\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{A}}^{\text{cdh}}(\lambda )=O(q^2/p)$, so solving CDH generically takes $\Omega (\sqrt{p})$ queries, matching baby-step giant-step — Sho97.

Sketch

Treat $x,y$ as indeterminates, answer group-oracle queries with random labels, record the affine polynomial each label represents, and choose $(x,y)$ only after the adversary halts. It wins only if two distinct recorded polynomials agree at $(x,y)$ or its output’s polynomial agrees with $xy$ there; each is the vanishing of a nonzero polynomial of degree at most $2$ at a uniform point of ${\mathbb{Z}}_p^2$, probability at most $2/p$, over $O(q^2)$ events.