>>13236020I assume you actually want to solve the Computational Diffie-Hellman (CDH) problem, where given g^a, g^b, and p, compute g^(ab), all numbers modulo p. This is what's used in crypto - Alice has a, Bob has b, and they both compute g^(ab) in the final step.
The discrete logarithm (DL) problem is different, that's saying given g, g^a, and p, find a. In fact, if we can solve DL, then we can certainly solve CDH (by finding a and b), but if we can solve CDH, it doesn't imply we can solve DL. This shows the two problems aren't the same in terms of difficulty, and could imply DL isn't necessary to solve CDH. We still don't know if finding a or b is a necessary step in solving CDH.
Anyways, there's two reasons I think these problems are intractable.
First of all, it was shown a few years ago that any algorithm that solves CDH in better than subexponential time can't rely on group properties or """standard""" arithmetic operations. It must use some sort of "meta" information, like the way group elements have been encoded - how we represent g^a and g^b. Don't remember the paper but it'll come to me eventually. Even if there was some magic trick that worked for, say, fields like Z_p, what about elliptic curves, or other objects with a ring structure?
Further, the discrete log family of problems has random self-reducibility. This means DL is either hard everywhere or hard nowhere (from a density perspective). Given an algorithm A that solves DL with probability 1/poly(n), we can amplify the success to arbitrarily high probabilities by constructing algorithm B like so:
>given g, g^x>pick random y>send g, g^(xy) to A>with prob 1/poly(n), get z = xy, compute x = y * z^-1>otherwise, go back to step 2.Note 1/poly(n) can be arbitrarily small, 1/n^100, 1/n^1000, 1/n^1e100, it doesn't matter. If there was an algorithm that solved DL with even near-negligible probability, then we could solve DL with near certainty.
