No free reduction from GGM to CDH

A reduction of class free from GGM to CDH would imply a contradiction.

Statement

Migrated verbatim from generic-group-model § Shoup’s Formulation:

The key result of Sho97 is that any generic algorithm solving DLOG, CDH, or DDH in a group of prime order $p$ must issue $\Omega (\sqrt{p})$ oracle queries. Combined with the Baby-step Giant-step algorithm, this is tight.

Migrated verbatim from computational-diffie-hellman § Known Results:

• In the Generic Group Model, ${\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{A}}^{\text{cdh}}(\lambda )\le O(\frac{q^2}{p})$, where $q$ is the number of queries that $\mathcal{A}$ issues — Sho97

Notes

Recorded during migration and not fixed — these are claims about the source text, not changes to it:

• Second of the three lower bounds bundled at line 23.
• Same caveat: this is unconditional hardness against generic algorithms, not a reduction from another assumption.
• Three near-identical copies of the same Sho97 theorem across dlog / ddh / cdh pages, differing only in the superscript on Adv. A fourth statement of the same bound sits at content/Glossary/generic-group-model.md:23 in the Omega(sqrt(p))-queries form rather than the O(q^2/p)-advantage form.
• This is a MODEL-RELATIVE LOWER BOUND, not a reduction barrier. It is a hardness result inside an idealized model, which the barrier schema shoehorns into consequenceKind ‘contradiction’. A separate ‘idealized-model lower bound’ record type would fit better.
• The DDH copy is the shakiest: the O(q^2/p) generic bound for DDH requires more care than for DLOG/CDH and the page states it identically to the other two without comment.