Join Log in
Score:6
LinusK avatar Crypto

Why is the discrete logarithm problem hard?

de flag
LinusK

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?

1417
0 + 0
kelalaka avatar
in flag
kelalaka
[Discrete Logarithm: Given a p, what does it mean to find the discrete logarithm of x to base y?](https://crypto.stackexchange.com/q/76230/18298)
2
Reply
WizardOfMenlo avatar
ph flag
WizardOfMenlo
Just a quick note, in fact you can compute the discrete log (in a general group) in $O(\sqrt{n})$ group operations (using, for example, Pollard Rho). See for example 'An Introduction to Mathematical Cryptography' section 5.5
0
Reply
Score:15
poncho avatar Crypto
my flag
poncho

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.

0 + 0
LinusK avatar
de flag
LinusK
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$?
0
Reply
poncho avatar
my flag
poncho
@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.
4
Reply
LinusK avatar
de flag
LinusK
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.
0
Reply
poncho avatar
my flag
poncho
@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)
3
Reply
sh flag
Paŭlo Ebermann
What is a "hard group"?
0
Reply
poncho avatar
my flag
poncho
@PaŭloEbermann: sorry, my changed how I wanted to express this as I wrote it, and an additional 'hard' stayed in. Does the edit make more sense?
0
Reply
sa flag
K.G.
Also, the generic group model does not capture quantum computation, which also seems to make it less useful than desired.
0
Reply
poncho avatar
my flag
poncho
@K.G.: true enough - even though (I believe) Shor's algorithm can work in an entangled black-box group implementation, that is a different computational model...
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.