Generic Group Model

The Generic Group Model (GGM) is a model for analyzing the security of group-based cryptographic assumptions. It restricts adversaries to those that cannot exploit any special properties of how group elements are represented, interacting with the group only through an oracle. The model goes back to Nechaev Nec94 and Shoup Sho97; Maurer Mau05 formalized the representation-free variant, and the two formulations differ in important ways.

Shoup’s Formulation

Let $(G, g, p) \leftarrow GrGen (1^{λ})$ be a cyclic group of prime order $p$ . A handle function is a random injection $σ : G \to {0, 1}^{n}$ , which assigns each group element a unique opaque bit-string called a handle. The adversary is only ever given handles — never actual group elements — and must compute via oracle queries:

Group operation: $O_{op} (σ (X), σ (Y)) \to σ (X \cdot Y)$
Inversion: $O_{inv} (σ (X)) \to σ (X^{- 1})$

Equality of group elements is implicit: since $σ$ is injective, two handles are equal iff the underlying elements are. An algorithm is generic (in Shoup’s sense) if it succeeds at a computational task for every choice of injection $σ$ .

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

Maurer’s Formulation

In Maurer’s formulation, group elements receive no representation at all, random or otherwise. The elements of a group of order $p$ , identified with $Z_{p}$ , are held in registers inside a black box; the adversary refers to them only by register index, may insert constants and ask the box to store the sum of two registers in a new register, and learns nothing except the answers to equality queries between registers.

This captures a different notion of independence from the group representation, and connects more naturally to the algebraic structure of $Z_{p}$ .

Comparing the Two Formulations

Jager and Schwenk JS08 argued that Shoup’s and Maurer’s formulations are equivalent for standard cyclic groups. However, Maurer, Portmann, and Zhu MPZ20 showed this is not generally true. They identify a key source of divergence: in Shoup’s model, the adversary can test equality of handles (implicitly, across all known elements at once), whereas Maurer’s label-free model encodes equality differently. MPZ20 establish a precise hierarchy of GGM variants — parameterized by the set of available queries — and show that the two original models occupy different positions in this hierarchy. Zhandry showed that Shoup’s model is equivalent to a type-safe variant of Maurer’s for single-stage games — Zha22.

The Structured GGM

Corrigan-Gibbs, Henzinger, and Wu CHW26 extend Shoup’s model to capture algorithms that exploit non-generic structure in a controlled way. In the structured GGM, the adversary may exploit special structure for at most a $δ$ fraction of group elements while remaining fully generic on the rest. The main result is that any DLOG algorithm in a group of prime order $p$ that exploits structure on at most a $δ$ fraction of elements requires time

Ω (min (p, \frac{1}{δ})) .

This yields tight subexponential lower bounds applicable to index-calculus algorithms, bridging the gap between fully generic lower bounds and structured algorithm analyses.

Comparison with the AGM

The Algebraic Group Model (AGM) is a strictly weaker idealization: every generic algorithm (in Shoup’s or Maurer’s sense) satisfies the AGM’s algebraic accountability condition, but not conversely. Security proven only in the AGM does not automatically imply security in the GGM.

Participates in

Builds on Generic Group Model

Barriers

No reduction from AGM to GGM

Proved in the Generic Group Model

Cryptology City

Explorer