# Subexponential algorithms for DLP in $\mathbb{Z}_s \times \mathbb{Z}_t$

Consider the accepted answer to the question: Why are elliptic curves better than cyclic groups?

It seems to suggest there are subexponential algorithms (i.e., algorithms with running time $$L_n[\alpha,c]=e^{(c+o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha}},$$ where $\ln n$ is the input size, $c > 0$, and $0 < \alpha < 1$) for solving DLP in $\mathbb{Z}_s \times \mathbb{Z}_t$ in general.

Are there such algorithms?

If not, perhaps someone could explain the following sentence that appears in the answer:

"And working only with the representation $\mathbb{Z}_s \times \mathbb{Z}_t$ will weaken the discrete logarithm so useful for cryptographic purposes."

• This question starts from a faulty premise. The accepted answer you link to does not suggest that there are subexponential algorithms for solving DLP in $\mathbb{Z}_s \times \mathbb{Z}_t$. (In fact I don't even see the word subexponential in that answer.)
– D.W.
Mar 18 '14 at 20:40
• I disagree that the premise is faulty. To me, the answer suggests a subexponential algorithm (I'll explain my reasoning in the next comment.) If the answer doesn't suggest that to you, then that's fine. Mar 18 '14 at 22:36
• In the answer the following sentence appears: "And working only with the representation $Z_s \times Z_t$ will weaken the discrete logarithm so useful for cryptographic purposes." I interpreted that sentence as suggesting that the DLP in $Z_s \times Z_t$ is easier to solve than in the corresponding elliptic curve group. In the corresponding elliptic curve group, the DLP is solvable in time $O(exp((1/2) \ln n))$. So if DLP is easier in $Z_s \times Z_t$, then it should be solvable faster than $O(exp((1/2) \ln n))$. In fact, I see now that DLP in $Z_s \times Z_t$ is essentially trivial. Mar 18 '14 at 22:36
• JasonJones, yup! It does suggest that the DLP is easier to solve than in the corresponding elliptic curve. It does suggest that the DLP can be solved faster than exponential time. The faulty premise is in assuming this means it is claiming that the DLP can be solved in sub-exponential time, e.g., in $L_n[\alpha,c]$ time.
– D.W.
Mar 18 '14 at 22:56
• Good point; faster than $O(\exp(c\ln n))$ does not imply $L_n[\alpha,c]$ with $\alpha < 1$. Mar 18 '14 at 23:51

First of all, DLP is only defined for cyclic groups. The $\mathbb{Z}_s^+ \times \mathbb{Z}_t^+$ you are talking about is not cyclic, since (say) $s$ divides $t$. But you can define a "generalized" DLP by considering the cyclic subgroup generated by an element $g$.

Next, DLP in any subgroup of $\mathbb{Z}_t^+$ is trivial. Figuring out why is a nice exercise. It follows that any "generalized" DLP in $\mathbb{Z}_s^+ \times \mathbb{Z}_t^+$ will be trivial. So there's no need to consider subexponential algorithms.

(If we were talking about $\mathbb{Z}_t^*$, not $\mathbb{Z}_t^+$, subexponential algorithms would be interesting and important.)

An elliptic curve has a group structure that is isomorphic to $\mathbb{Z}_s^+ \times \mathbb{Z}_t^+$ (for some $s$ and $t$), which means that abstractly, the two mathematical objects have the same structure. But they have different representations.

Representation is extremely important for DLP. As far as anyone knows, "generalized" DLP is hard when the representation is a suitably chosen elliptic curve, but it is extremely easy when the representation is $\mathbb{Z}_s^+ \times \mathbb{Z}_t^+$. Abstractly, they're the same, but in practice, they are very different with respect to what we can compute. For instance, recovering the isomorphism that connects the elliptic curve to $\mathbb{Z}_s^+ \times \mathbb{Z}_t^+$ (that maps from one representation to the other) is computationally hard: it is as hard as the discrete log problem on that elliptic curve.

PS. The above contains many mathematical subtleties, so please consider this as an invitation to study mathematics, and not as an answer to your questions.

Please let me know if I have something wrong here.

Let $g \in \mathbb{Z}_s^{+}$ be fixed in advance.

Choose any $h$ in $<g> = \{g,2g,3g,\ldots \}$, the (finite) cyclic subgroup of $\mathbb{Z}_s^{+}$ generated by $g$. Then $$h = xg$$ for some $x \in \{0,\ldots,s-1\}$. In fact, $x \in \{0,\ldots,\text{order}(g)-1\} \subseteq \{0,\ldots,s-1\}$. The discrete logarithm problem is to find $x$ given $h$.

If $g = 0$, then $h = 0$ and any $x \in \{0,\ldots,s-1\}$ is a solution. This case is really trivial.

If $g \neq 0$, then we can find the multiplicative inverse $g^{-1}$ in $\mathbb{Z}_s^{\times}$ in advance. Then $x = hg^{-1}$. This case is nearly as trivial. Note that this is much better than computing $xg$ for all possible $x \in \{0,\ldots,\text{order}(g)-1\}$ until we hit $h$, which is essentially the best known algorithm for solving the DLP in an arbitrary group.

The key here is that we are really working in the ring $(\mathbb{Z_s},+,\times)$. The additional multiplicative structure this ring provides compared to the group $\mathbb{Z_s}^{+}$ makes the DLP in $\mathbb{Z_s}^{+}$ trivial.

For the discrete log problem in the group $\mathbb{Z}_s^{\times}$ we also have the ring $(\mathbb{Z_s},+,\times)$ to work with, but the additional additive structure helps less for finding $x$ such that $g^x = h$ for any $h$. However, additive structure does help. Because we have a (nice) ring, we have prime elements and a fundamental theorem of arithmetic. This lets us use the index calculus algorithm to solve the the DLP in $\mathbb{Z}_s^{\times}$.

For the discrete logarithm problem in an elliptic curve group, we have less structure to exploit to help solve the DLP.

Now we consider the situation in $\mathbb{Z}_s^{+} \times \mathbb{Z}_t^{+}$.

Let $g = (g_1,g_2) \in Z_s^{+} \times Z_t^{+}$ be fixed in advance.

Choose any $h=(h_1,h_2)$ in $<g> = \{g,2g,3g,\ldots \}$, the (finite) cyclic subgroup of $\mathbb{Z}_s^{+}$ generated by $g$. Then $$h = xg$$ for some $x \in \{0,\ldots,\text{order}(g)-1\} \subseteq \{0,\ldots,s-1\}$. The discrete logarithm problem is to find $x$ given $h$.

The equation $h = xg$ is equivalent to $(h_1,h_2) = (xg_1,xg_2).$ If $g_1$ is non-zero, we compute $g_1^{-1} \in \mathbb{Z}_s^{\times}$ in advance. Then $x = h_1 g_1^{-1}$. Easy. If $g_2$ is non-zero, we can find $x$ analogously. If $g = 0$ the problem is trivial as above.

• This is reasonably correct. One quibble: Can $h_1g_1^{-1}$ and $h_2 g_2^{-1}$ be different?
– K.G.
Mar 19 '14 at 8:18
• They can, but they will be congruent modulo $\min(s,t)$. Good point. Mar 19 '14 at 23:14