Generic Group Model

From Koblitz-Menezes: https://eprint.iacr.org/2006/230.pdf In the ring of integers modulo an RSA-modulo N or the multiplicative group of a finite field, there are subexponential-time index calculus algorithms that solve the underlying hard problems (such as discrete-log). However, for a suitably chosen elliptic curve, there are no such subexponential-time algorithms.

Hence, algorithms that do not use the special structure of the Elliptic Curve Group, but treat all groups as the same, are known as "generic". Pollard's rho and Shank's 'baby-step/giant-step" algorithms are two such examples, requiring O(\sqrt(q)), where q is the order of the largest prime-order subgroup.

Shoup showed that faster "generic" group algorithms do not exist and introduced the "generic group model" in the process.

The "generic group model" proposes that there is an "oracle" that works as follows on two types of inputs: 1. Type 1: An integer i, 0<=i<q. In this case, the oracle outputs encoding \sigma(i) and keeps a record of it. If i has already been queried, the same encoding is returned. Otherwise, \sigma(i) is chosen randomly.

2. 4-tuple r,s,\sigma(i),\sigma(j), where 0<=r,s<q and \sigma(i), \sigma(j) are outputs from earlier queires. The oracle returns \sigma(ri+sj mod q) as before. If the value has been seen before, it returns the same one, otherwise it returns a randomly chosen one different from earlier values.