0
$\begingroup$

This question already has an answer here:

The multiplicative group mod $p$ is isometric to the additive group mod $p-1$, yet computing discrete logarithms in the additive group is easy and completing discrete logarithms in the multiplicative group is usually hard.

What is it about group representation that makes group representation matter so much for the complexity of computing discrete logarithms?

$\endgroup$

marked as duplicate by kelalaka, AleksanderRas, Maarten Bodewes Aug 21 at 11:04

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

4
$\begingroup$

Well, the group being isomorphic doesn't imply that the isomorphism is efficiently computable. If $G \simeq H$ via $\phi : G \rightarrow H$ and $\phi$ is computable, then indeed, DLOG is no harder in $G$ than in $H$ because you can transform the instance.

In the case you mentioned, we have $G = \mathbb Z/(p-1) \mathbb Z$ and $H = (\mathbb Z/p\mathbb Z)^\times$. A efficient morphism $\phi: G \rightarrow H$ is known, it called `fast exponentiation'. So DLOG is no harder in $G$ than it is in $H$. But computing a reversed morphism $\psi: H \rightarrow G$ seems harder...

$\endgroup$
1
$\begingroup$

The prototypical example of a group in cryptography is a cyclic group. You can write this in a variety of ways, so I'll go through a few quickly.


Additively: Consider the group $\mathbb{Z}/n\mathbb{Z}$ under $+$. This forms a group, and it's a cyclic group generated by $\langle 1\rangle$ (subject to the relation that $n\cdot 1 = 0$). Note that the "exponentiation" in this group is the group operation repeated (so multiplication).

How hard it is to compute the discrete logarithm in this group depends on how you particularly store group elements, but a naïve implementation is storing them as an element of $[n]$. Under this convention, the discrete log is immediate --- $\mathsf{log}_1(n) = n$, so it can be compute in $O(1)$ time under a very natural storage mechanism.

Multiplicatively:

Now, consider the group $\mathbb{F}_{p}^*$, where $|p| \approx. \log_2 p = n$. Say that $p$ is a "safe prime", so $p - 1 = 2q$ where $q$ is prime. Let this be generated by $g$. What's the complexity of computing the discrete logarithm here? If we store elements via their representation as a number in $[n]$ it's unclear. The best (asymptotically) algorithms end up being the General Number Field sieve, which is sub-exponential. The cost of it is slightly complicated (you can set parameters differently to get different costs), but should broadly be thought of as very roughly $\exp(O(\sqrt[3]{n}))$.

Elliptic-curve-ly:

Being slightly vague, the set of rational points on an elliptic curve forms a group, so we can look at the cyclic group generated by some particular element. What's the running time of it?

To the best of my knowledge, there are no special-purpose algorithms known to give improvements over general-purpose algorithms in this case (the best attacks against the DL in EC groups are general attacks). This is formalized in the generic group model (see for example this paper). Essentially, some algorithms (like the ones mentioned in the above sections) exploit particular ways group elements are represented for speed improvements. For algorithms that don't (which are known as "generic"), there is a lower bound of $\Omega(p^{1/2})$ group operations to compute a discrete log in a cyclic group of order $n$, where $p$ is the largest prime divisor of $n$.

To learn more about this, you should look into the "Generic Group Model", which is the formal way such lower bounds are proven (and a way to think about how useful the "structure" in a given group is to solve computational problems in the group --- if a given algorithm can be written in the same complexity within the generic group model, the structure isn't useful at all).

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.