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?

$\endgroup$
2

1 Answer 1

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.

$\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 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 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 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 at 14:33
  • $\begingroup$ What is a "hard group"? $\endgroup$ Apr 3 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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