Generic Group Model - Revision history

Srikar at 18:25, 15 July 2020

2020-07-15T18:25:38Z

Srikar: /* Context */

2020-07-15T18:25:20Z

Context

Srikar at 18:25, 15 July 2020

2020-07-15T18:25:06Z

Srikar: Created page with "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 subexponenti..."

2020-07-15T18:24:21Z

Created page with "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 subexponenti..."

New page

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.

← Older revision		Revision as of 18:25, 15 July 2020
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==

@@ Line 5: / Line 5: @@
 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==

@@ Line 1: / Line 1: @@
 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.
@@ Line 6: / Line 7: @@
 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:
 . 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.
 . 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.