Why is it difficult to develop a subexponential functoral approach to discrete log
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.