# Difference between Generic Group Models

I'm trying to understand the difference between the (classical) Generic Group Model as it is described by Shoup [Shoup] and the somewhat restricted Generic Group Model as it is described by Schnorr and Jakobsson in [SJ00]. For clarity, I'm going to give the definition of the two models. For that, I'm using the explanations of the Paper [BL19]. In both settings, we have a multiplicative cyclic group $$G = \langle g \rangle$$ of order $$p$$. (GGM = generic group model)

1. Shoup's Generic Group Model

Since $$G$$ is isomorphic to $$\mathbb{Z}_p$$, we can select a random injective map $$\tau: \mathbb{Z}_p \rightarrow \mathbb{G}$$, where $$\mathbb{G}$$ is the set of bit strings of length $$l \ (2^l \geq p)$$ and we encode the discrete log of the group element instead of the group element itself. The key idea is that the map $$\tau$$ does not need to be a group homomorphism. The GGM assumes that an adversary has no access to the concrete representation of the group elements. Instead, the adversary is given access to an oracle parametrized by $$\tau$$, which computes the group operations indirectly in $$G$$. More precisely, for an input $$(a,b) \in \mathbb{G} \times \mathbb{G}$$ the oracles act as follows $$Mult(a,b) = \tau(\tau^{-1}(a) + \tau^{-1}(b)), \ Inv(a) = \tau(-\tau^{-1}(a))$$. We remark that the adversary has no access to the map $$\tau$$ itself.

1. Schnorr and Jakobssen GGM based on collisions

The data of the generic algorithm is partitioned into group elements from $$G$$ and non-group data. A generic step is $$mexp: \mathbb{Z}^d_q \times G^d \mapsto G, (\underline{a}, (f_1,...,f_d)) \mapsto \prod_{i=1}^d f_i^{a_i}$$. Formal definition: A generic algorithm is a sequence of $$t$$ generic steps; for time $$1 \leq t' < t$$, the algortihm takes inputs as $$f_1,...,f_{t'}$$, where $$(a_1,...,a_{i-1}) \in \mathbb{Z}^{i-1}_p$$ depends arbitrarily on i, the non group-element and the set $$CO_{i-1} := \lbrace (j,k) | f_j = f_k, 1 \leq j of previous "collisions" of the group.

The main difference seems to be that the attacker in Shoup's model is given a direct handle $$\tau(g)$$ for any group element that is the output of any generic group query. While the attacker in the second model may only indirectly reference previously computed group elements by submitting a query $$(a_i, ..., a_{i-1}) \in \mathbb{Z}_p^{i-1}$$ to the generic group oracle. But these two definitions just seem so different to me that I would really appreciate it if someone could help me point out the differences and the similarities. In particular, I would like to understand the advantages of security proofs in Shoup's model compared to security proofs in Schnorr's model.

Both models have the same "computational power" : You can build $$Mult$$, and $$Inv$$ routines with $$mexp$$, and you can build $$mexp$$ with $$Mult$$ (by using square-and-multiply algorithm).
We can think that in the second model the adversary has access to the real value of the element, but it can use it to have a better efficiency because the coefficients $$f_i$$ could not depend of these values (except if there is equality detected like in the first model).