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
Computational Diffie Hellman problem wants to know $g^{ab}$ given $g^a$, $g^b$ and $g$ while the discrete logarithm problem wants to know $x$ from $g^x$ and $g$.
The latter resolvable in polynomial-time implies the former as well but a converse result is not known.
What are the consequences to cryptography if Diffie-Hellman is breakable but an algorithm for discrete logarithm is unclear?
There is a big question (that Meir Maor hints at) underlying your problem, namely:
Must the algorithm work for a fixed group, or any group?
Note that there exist groups for which DLOG (and things that reduce to DLOG) are easy, the most basic example is the group $(\mathbb{Z}/n\mathbb{Z}, +)$. Even among groups that have been used within cryptography, there are groups for which DLOG (and things that reduce to DLOG) are now much easier than we used to think they were --- specifically the group $(\mathbb{F}_{p^n}^\times, \times)$ for $p = O(1)$ admits quasi-polynomial time DLOG algorithms --- this paper shows expected time $(pn)^{2\log_2(n) + O(1)}$. This weakness isn't just theoretical, by far the largest DLOG computed was in $\mathbb{F}_{2^{30750}}^\times$.
Of course, this is all about the discrete logarithm problem. There are (in my eyes) two other natural questions:
For the first problem, this is unlikely to happen. This is because in the Algebraic group model the problems are equivalent. This model restricts computations somewhat (the DLOG algorithm for $\mathbb{F}_{2^{30750}}^\times$ is not expressible within it), but the restriction is somewhat natural --- computations are seen as a (linear) sequence of steps, and any group elements used in step $i$ must be explicitly computed from group elements used in prior steps. There are some nuances here I am not entirely familiar with [1], but the point of the model is to capture algorithms that only use the "public API" of the group, instead of specific details about the structure of the group.
This means that if DLOG and CDH are not equivalent for general groups, the model is quite flawed in capturing the "public API" part of group-theoretic computations, which is perhaps not obvious (to me at least) from examining the model.
For the second problem, this is also not likely to happen (but for other reasons). Specifically, the two problems are known to be non-uniformly equivalent to eachother over arbitrary cyclic groups. See my prior answer for details.
Neither of these two points absolutely rules out a separation between CDH and DLOG, but both provide some formal evidence that such a separation is unlikely to happen.
[1] Specifically, what group elements do you start with? The group identity seems natural, but discussion at the bottom of page 7 sounds like you get random oracle queries too. Is there anything else?
There are very few consequences. In fact it is fairly likely Discrete logarithm is in P, or at least it is not likely to be NP hard. Discrete logarithm is random self reducible which is one of the reasons we like it. A random instance is as hard as the worst case.
Sadly the existence of an NP-Hard random self reducible problem implies the collapse of the polynomial heirarchy and this is believed not to be the case.
So despite having convincing arguments that Diffi Helman is not "Hard" we still use it. Since we know of no efficient algorithm to break it and we have been looking hard for a while, that's really as good as you get in cryptography.
Note we can rank possible events:
The first will make a stir in academic community but won't actually surprise anyone. The second may cause frantic replacement of DH based algorithms which are everywhere. The third will break the internet.
Also impact will be different for a general solution over any Field/Ring or e.g only for Zp.
