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)
- 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.
- 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 <k \leq i-1 \rbrace $ 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.
Many thanks in advance!
