Why is it difficult to develop a subexponential functoral approach to discrete log Call a discrete logarithm algorithm functoral if the commutative algebraic object that the algorithm acts on can be changed with another commutative object in the same category and the algorithm does not asymptotically slowdown.

Why is it difficult to develop a single functoral discrete logarithm (classical) algorithm that works on all commutative groups?
The reason that sub exponential algorithms for the discrete log in $\mathbb{Z}/p\mathbb{Z}$ do not carry over to groups based on elliptic curves is because $\mathbb{Z}/p\mathbb{Z}$ has extra structure that doesn't seem to be present in elliptic curve groups.

In particular, $\mathbb{Z}/p\mathbb{Z}$ has both addition and multiplication, whereas the elliptic curve groups have only one operation.  The sub exponential algorithms for the discrete log in $\mathbb{Z}/p\mathbb{Z}$ make essential use of this: the extra structure allows us to define the notion of a smooth integer.  A smooth integer is an integer that factors into small primes; here the notion of "small" makes use of this additional structure (namely, the addition operation).  This notion of smoothness is critical to the effectiveness of the sub exponential algorithms for $\mathbb{Z}/p\mathbb{Z}$.

Any discrete log algorithm that relies upon "smoothness" (or this additional structure) is therefore not going to be "functoral".  A consequence is that the best existing techniques we know of for computing the discrete log in $\mathbb{Z}/p\mathbb{Z}$ are not functoral and do not carry over to elliptic curve groups.

Why is it hard to develop an efficient functoral algorithm for the discrete log in $\mathbb{Z}/p\mathbb{Z}$?  Because if you want it to be functoral, you're disallowing use of smoothness, which is essential to all known techniques.

See, e.g., http://en.wikipedia.org/wiki/Index_calculus_algorithm and http://en.wikipedia.org/wiki/Number_field_sieve.



Here is a second hurdle to functoral algorithms.  There are known lower bounds on the discrete log problem in "black box" groups.

A black box group is one where we do not have an explicit representation of group elements.  Instead, all we have are a few black boxes: a black box that, given two group elements, returns their product; a black box that, given a group element, returns its inverse; a black box that returns a random element of the group; and so on.  In particular, in a black box group, you cannot do something like "look at the third bit of the representation of the group element and branch based upon whether it is 1 or 0".  You also can't access any additional structure (since you're only given a black box for the group operation; it's a black box group, not a black box ring).

In this setting, it is known that, if the group is of order $p$ where $p$ is a prime, there is no generic algorithm for the discrete log whose running time is better than $\Theta(\sqrt{p})$.  I'm not 100% clear on how you plan to define "functoral", but it looks to me like this implies you cannot expect a functoral algorithm whose running time is sub exponential.

See, e.g., the following paper:


Lower Bounds for Discrete Logarithms and Related Problems.  Victor Shoup.  EUROCRYPT '97.