What is the discrete logarithm assumption and why it is not easy with Shank's baby-step/giant-step

When I read about the DLP, it seems that the assumption is that it is not generally possible to solve it in polynomial time. But I also read that there are several algorithms in $$\mathcal{O}(\sqrt{n})$$, for instance, the Shank's baby-step/giant-step so there must be some misunderstanding by me.

• What is the assumption?

If I understand the problem correctly, we are given a group with a modulus and a generator of that group. The problem is:

• Given an element $$x$$ of the group, find the number $$a$$ so that the generator $$g$$ will generate $$x$$ by $$x = g^a \bmod q.$$ And the assumption is that we cannot do it for a random or worst instance of the problem in polynomial time, but I must have misunderstood because I read about deterministic algorithms such as Shank's baby-step/giant-step which solve the problem in $$\mathcal{O}(\sqrt{|G|})$$ which is quite fast isn't it?

Where is my mistake?

• – kelalaka May 16 '20 at 21:42

3 Answers

When I read about the DLP, it seems that the assumption is that it is not generally possible to solve it in polynomial time.

Actually, whether or not we assume that it is hard depends on the group; there are certainly groups where it is quite easy (for example, in $$\mathbb{Z}_q^*$$ where $$q-1$$ is smooth).

But I also read that there are several algorithms in O(sqrt(n)) for instance the big-step/baby-step so there must be some misunderstanding by me.

That is what you are misunderstanding; when we say "polynomial time", we mean "polynomial in $$\log(n)$$"; $$\sqrt{n}$$ is not polynomial in $$\log(n)$$ (actually, it is exponential), and so that is not a contradiction.

The problem is: Given an element $$x$$ of the group, find the number $$a$$ so that the generator $$g$$ will generate $$x$$ by $$x = g^a \bmod q$$.

Actually, there are a number of generalizations, and they're all sometimes called DLP:

• Perhaps we don't require $$g$$ to be the generator of the entire group; we still insist that $$x$$ be a member of the subgroup that $$g$$ generates (there won't be an $$a$$ otherwise). This is actually more common than your meaning; where $$g$$ might generate a prime-sized subgroup.

• Perhaps we don't restrict ourselves to groups of the form $$\mathbb{Z}_q^*$$, but instead have $$g$$ and $$x$$ be members of a different group (for example, an elliptic curve group). Sometimes this is called the ECDLog problem; sometimes, we aren't as specific.

I read about deterministic algorithms such as Shank's which solve the problem in O(sqrt(|G|) which is quite fast isn't it?

Not if $$|G| > 2^{256}$$, it's not (and yes, that's the size of the groups we use in practice)

But I also read that there are several algorithms in O(sqrt(n)) for instance the big-step/baby-step so there must be some misunderstanding by me.

The algorithm you mention runs in time $$O(\sqrt{|G|})$$ and the groups are usually chosen such that $$|G|\approx 2^{\lambda}$$ for some security parameter $$\lambda$$. Therefore, the run-time of the algorithms is $$O(2^{\lambda/2})$$, which is still exponential in the security parameter.

What is the assumption?

For a cyclic group $$G$$ of order prime order $$p$$ (where $$|p|\approx 2^\lambda$$) and a generator $$g$$ the discrete-logarithm problem is defined as follows:

Input: $$g^a\in G$$ for $$a\leftarrow \mathbb{Z}_q$$ (i.e., randomly-chosen $$a$$)

Solution: $$a\in\mathbb{Z}_q$$

The assumption is that this problem is hard to solve for any (probabilistic) algorithm that runs in time polynomial in $$\lambda$$. One could also define DLP where the generator is also chosen uniformly at random: you can read more about the differences in [BMZ].

And the assumption is that we cannot do it for a random or worst instance of the problem in polynomial time,

The discrete-logarithm problem has a nice property that it is random self-reducible and therefore solving a random instance is at least as hard a solving a worst-case instance.

[BMZ]: Bartusek, Ma and Zhandry link, The Distinction Between Fixed and Random Generators in Group-Based Assumptions, Crypto'19

Note that $$O(\sqrt{|G|})=O(2^{0.5\log(|G|)})$$ is exponential in the input size $$\log(|G|)$$ and thus DL for a generic group is much harder (as far as known) than factoring for the same input size.

Factoring has subexponential but superpolynomial complexity which looks essentially like $$O(2^{(\log |G|)^a (\log\log(|G|))^{1-a}})$$ where $$a=1/3$$ for the number field sieve.

As pointed out in the comments

while DLOG for generic groups is thought to be difficult (and there are certain groups, in particular elliptic curve groups, which are thought to be generic), DLOG over subgroups of the multiplicative group of a finite field (for example $$Z_p^\ast$$) admits similar "subexponential but superpolynomial" algorithms (one can in fact use index calculus algorithms still, which the number field sieve is a particular case of).

• It's worth mentioning that while DLOG for generic groups is thought to be difficult (and there are certain groups, in particular elliptic curve groups, which are thought to be generic), DLOG over subgroups of the multiplicative group of a finite field (for example $\mathbb{Z}_p^*$) admits similar "subexponential but superpolynomial" algorithms (one can in fact use index calculus algorithms still, which the number field sieve is a particular case of). – Mark May 16 '20 at 22:59