Difference between revisions of "Generic Group Model"
| Line 12: | Line 12: | ||
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. | 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. | ||
| + | |||
| + | ==References== | ||
Latest revision as of 18:25, 15 July 2020
Context
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.
Definition
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.
