Difference between Generic Group Models

Question

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.

2. 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!

Answer 1

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).

For me the only differences is the non-uniformity of the second model (the second model seems like a circuit to me, contrarily to the first one which is more like a Turing Machine with an oracle), and the time-complexity :

You can't compare time complexity of two algorithms in both models easily, because some operations (exponentiation for example) are much faster considered in the second model as in the first one. Thus probably the lower bounds with the first model would be bigger/better (and still relevant as far I know Elliptic curve operations are made in practice).