Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I am novice here. I am following a lecture series of Prof. Christof Paar and in his lecture of DLP, he states a fact which I did not understand at all. Can somebody please explain it better to me.I understand DLP and DHP independently. The statement goes as follow:
"If the only way of solving the DHP requires the DLP, one would say that, the DHP is equivalent to the DLP" However this is not proven yet.
Also he says that if somebody proves it, it would be ground breaking research.
DH for reference:
- Alice takes a random $a$ and sends $g^a$ to Bob.
- Bob picks a random $b$ and sends $g^b$ to Alice.
- Both compute $g^{ab}$ Alice as $(g^b)^a$, Bob as $(g^a)^b$.
As you already explained breaking DLOG will break DH in the following way:
An attacker can e.g.
At this point the attacker knows the shared secret $g^{ab}$ and DH is broken.
However what about the other way around? Does breaking DH mean that we can compute DLOGs? The situation is not so clear...
Breaking DH means that the attacker is given $g, g^a, g^b$ and is able to find the shared secret $g^{ab}$.
The question is can we somehow leverage this knowledge of $g^{ab}$ to find $a$ or $b$.
For a given group and generator $g$, the DLP is finding randomly chosen $x$ given $a=g^x$; and the DHP is finding $g^{(x\,y)}$ given $a=g^x$ and $b=g^y$, for randomly chosen $x$ and $y$.
It is known a method solving the DHP given an oracle capable of solving the DLP: find $x$ from the given $g^x$ using the oracle, then compute ${\left(g^y\right)}^x$, which is the desired $g^{(x\,y)}$. In other words, the DHP is no harder than the DLP.
It is not known any method solving the DLP given an oracle capable of solving the DHP. And thus we do not know if the DHP is easier than the DLP, or equivalent.
The citation in the question is
If the only way of solving the DHP requires the DLP, one would say that, the DHP is equivalent to the DLP
and that's clearly correct: if solving the DHP required solving the DLP (for $x$, or for $y$, or for an otherwise random instance of the DLP), then the DHP would be no easier than the DLP; and since the DHP is no harder than the DLP, the two would be equivalent.
However "the only way of solving the DHP requires the DLP" is false, or at least a gross oversimplification; making the quoted statement moot. Counter example: let $u\gets g$ and $v\gets b$; while $u\ne a$ repeat $u\gets u\,g$ and $v\gets v\,b$; output the final $v$, which is the desired $g^{(x\,y)}$.
Another observation is that the best known methods for solving the DHP involve solving a random instance of the DLP. And it there was a significantly better method, it would prove that solving the DHP is easier than the DLP. That might be a better statement of what is meant by the citation.
