6
$\begingroup$

Why is the discrete logarithm problem assumed to be hard?

Someone else asked the same question but the answers only explain that exponentiation is in $O(\log(n))$ while the fastest known algorithms to compute discrete logarithms is in $O(n)$. (I'm glossing over details like the runtime of index calculus here.)

Somewhere else I read: "We assume discrete logarithms to be hard because for over 40 years very smart people failed to find a fast algorithm."

Now, I wonder if there are any better arguments. Can you actually explain why discrete logarithms are hard?

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
15
$\begingroup$

Now, I wonder if there are any better arguments.

Ultimately, no, not really.

We don't have any proof that computing discrete logs is hard. For that matter, we don't have any proof that any problem within $NP$ (that is, any problem where, if the answer is "yes", there is a quickly checkable proof of that) is hard.

We do have some partial proofs, for example, that in the "black-box" model, a discrete log on a prime-order group is hard. On the other hand, the assumptions that makes is known to be false for finite-fields, and so that's less useful than one would hope.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Can't you argue, for example, along the lines that during exponentiation each of the $\log(n)$ squarings deletes a bit of information because $x \cdot x == -x \cdot -x$? $\endgroup$
    – LinusK
    Apr 2, 2022 at 13:38
  • 4
    $\begingroup$ @LinusK: not really; if $g$ has order $q$, then $g^x$ for $x \in \{0, ..., q-1\}$ is injective - that is, it doesn't lose any information. And so, while a common implementation substep (squaring) may lose information, overall there is no information loss. $\endgroup$
    – poncho
    Apr 2, 2022 at 14:10
  • $\begingroup$ But if $\mathbb{F}_p$ with $p=2q+1$ and $g$ has order $q$, then $g^x$ for $\{0,...,p-1\}$ is not injective. And if $g^{x_1} == g^{x_2}$ for some $x_1 \neq x_2$ then both the lowest bit of $x_1$ and $x_2$ (the hardcore bits) must be different. That's why I thought there must be some information loss. $\endgroup$
    – LinusK
    Apr 2, 2022 at 14:31
  • 3
    $\begingroup$ @LinusK: however, in that case, $x_1 \equiv x_2 \pmod q$; hence there is essentially only one solution (knowing that immediately gives you all the others) $\endgroup$
    – poncho
    Apr 2, 2022 at 14:33
  • $\begingroup$ What is a "hard group"? $\endgroup$
    – Paŭlo Ebermann
    Apr 3, 2022 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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