<p>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.</p>

<p>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}$.</p>

<p>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.</p>

<p>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.</p>

<p>See, e.g., <a href="http://en.wikipedia.org/wiki/Index_calculus_algorithm">http://en.wikipedia.org/wiki/Index_calculus_algorithm</a> and <a href="http://en.wikipedia.org/wiki/Number_field_sieve">http://en.wikipedia.org/wiki/Number_field_sieve</a>.</p>

<hr>

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

<p>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).</p>

<p>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.</p>

<p>See, e.g., the following paper:</p>

<ul>
<li><a href="http://www.shoup.net/papers/dlbounds1.pdf">Lower Bounds for Discrete Logarithms and Related Problems</a>.  Victor Shoup.  EUROCRYPT '97.</li>
</ul>

CC BY-SA 3.0
2013-12-19T20:28:33.717Z
Nice answer. Can you add references for people who might want to read more on these two?
Kaveh
CC BY-SA 3.0
2013-12-19T22:49:54.263Z
I like the first answer - so the key to any breakthrough seems to be getting an algorithm that does not rely on smoothness (or any other group specific structure). I am unsure if the second explanation provides any insights.
Turbo
CC BY-SA 3.0
2013-12-19T20:21:51.890Z
2013-12-19T20:51:00.347Z
2013-12-19T20:51:00.347Z
D.W.
<p>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.</p>

<p>Why is it difficult to develop a single functoral discrete logarithm (classical) algorithm that works on all commutative groups?</p>

CC BY-SA 3.0
2013-12-19T09:57:53.837Z
The discrete logarithm problem is an extensively studied question with rich literature. It's not clear to me how well you are aware of the relevant background. Can you give any references to the notion of _functorality_ and why it might be relevant to this problem? It's hard to develop a DL algorithm that works well on a **single** commutative group. Why should this notion help?
cody
CC BY-SA 3.0
2013-12-19T10:08:55.007Z
" It's hard to develop a DL algorithm that works well on a single commutative group" I am aware of this and I am also aware of a probabilistic algorithm that works in subexponential time for cyclic groups. "Why should this notion help?" Well this is the question why does this not help in say when we deal with group structure over Elliptic curves where a probablistic subexponential algorithm is not known.
Turbo
CC BY-SA 3.0
2013-12-19T12:40:28.307Z
What I am advocating is that you modify your question to give some background and motivation for it. In particular you should give background definitions and references in more detail, and point to papers if there are any you have in mind. It might also be wise to explain what it means to "change an algorithm". Possibly your question could be rephrased in a simpler way: "Why do probabilistic subexponential algorithms for DL in cyclic groups not carry over to groups based on elliptic curves?"
cody
CC BY-SA 3.0
2013-12-19T22:11:50.900Z
@cody actually no I do not want my answer to be group specific. I would like my answer to be providing an overall principle why such an approach would fail. Why is there no one algorithm for DLOG for comm groups? (something in sprit like why a new idea is required to solve an NP problem and why there is no one uniform efficient algorithm).
Turbo
CC BY-SA 3.0
2013-12-19T22:39:18.257Z
I thought the quantum algorithm worked for all commutative groups. Why do you say it doesn't?
Peter Shor 
CC BY-SA 3.0
2013-12-19T22:49:07.680Z
@PeterShor You are right. It works over all commutative groups. I will correct myself. Is there a analogous hope for classical algorithms?
Turbo
<ds.algorithms><algebra>
Why is it difficult to develop a subexponential functoral approach to discrete log
Turbo
# Why is it difficult to develop a subexponential functoral approach to discrete log

(Asked by: username_0 on 2013-12-19)

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?

**Tags:** ds.algorithms, algebra

> **Comments:**
> **username_1**: The discrete logarithm problem is an extensively studied question with rich literature. It's not clear to me how well you are aware of the relevant background. Can you give any references to the notion of _functorality_ and why it might be relevant to this problem? It's hard to develop a DL algorithm that works well on a **single** commutative group. Why should this notion help?  
> **username_0**: " It's hard to develop a DL algorithm that works well on a single commutative group" I am aware of this and I am also aware of a probabilistic algorithm that works in subexponential time for cyclic groups. "Why should this notion help?" Well this is the question why does this not help in say when we deal with group structure over Elliptic curves where a probablistic subexponential algorithm is not known.  
> **username_1**: What I am advocating is that you modify your question to give some background and motivation for it. In particular you should give background definitions and references in more detail, and point to papers if there are any you have in mind. It might also be wise to explain what it means to "change an algorithm". Possibly your question could be rephrased in a simpler way: "Why do probabilistic subexponential algorithms for DL in cyclic groups not carry over to groups based on elliptic curves?"  
> **username_0**: @username_1 actually no I do not want my answer to be group specific. I would like my answer to be providing an overall principle why such an approach would fail. Why is there no one algorithm for DLOG for comm groups? (something in sprit like why a new idea is required to solve an NP problem and why there is no one uniform efficient algorithm).  
> **username_2**: I thought the quantum algorithm worked for all commutative groups. Why do you say it doesn't?  
> **username_0**: @PeterShor You are right. It works over all commutative groups. I will correct myself. Is there a analogous hope for classical algorithms?  

---

## 1 answers

### Answer by username_3 on 2013-12-19. Score: 8

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](http://www.shoup.net/papers/dlbounds1.pdf). Victor Shoup. EUROCRYPT '97.

> **Comments:**
> **username_4**: Nice answer. Can you add references for people who might want to read more on these two?  
> **username_0**: I like the first answer - so the key to any breakthrough seems to be getting an algorithm that does not rely on smoothness (or any other group specific structure). I am unsure if the second explanation provides any insights.  

---

