Is there a group where CDH is easy but DLog is hard?

Question

The question is quite simple:

Is there a group where solving the CDH problem can be shown to be easy but solving the discrete logarithm problem is assumed to be hard?

---

Refresher on the problems:

• CDH: Let $\mathbb G=(G,+,0,p)$ be a public cyclic group of order $p$. Given any $g\in G$ and $g^a,g^b$ with $a,b\stackrel{\$}{\gets}\{0,\ldots,p-1\}$, that is with uniformly random exponents, find $g^{ab}$.

• DLog: Let $\mathbb G=(G,+,0,p)$ be a public cyclic group of order $p$. Given any $g\in G$ and $g^a$ with $a\stackrel{\$}{\gets}\{0,\ldots,p-1\}$, that is with a uniformly random exponent, find $a$.

Answer 1

There are some known groups in which computational Diffie-Hellman assumption is equivalent to discrete logarithm problem. Besides, It has been shown that the equivalence holds "when a small amount of extra information depending on the group order is provided". Furthermore, those extra informations has been computed for certain elliptic curve groups used in real cryptographic applications. Later the reduction has been tightened.

The whole progress in researches shows that although there is no full proof for the equivalence but there are some evidences which lead to the believe that there might not be any groups in which computational Diffie-Hellman is easy but discrete logarithm problem is hard.

Answer 2

Here is something that is close but not exactly what you're asking for. But it may be enough for what you have in mind.

This paper uses indistinguishability obfuscation to construct a group with self-bilinear map -- i.e., a map $e : G \times G \to G$ (same source & target groups).

Yamakawa et al., Self-bilinear Map on Unknown Order Groups from Indistinguishability Obfuscation and Its Applications, CRYPTO 2014.

Although I don't completely understand their hardness assumption, and they don't explicitly talk about discrete log, the fact that the "obvious" generalization of Diffie-Hellman gives secure multi-party non-interactive key agreement suggests that discrete log must be hard.

Unfortunately, having a self-bilinear map $e : G \times G \to G$ is not quite the same as a CDH solution! Indeed, their construction uses $e(g^x, g^y) = g^{2xy}$ which is bilinear, but they are in (a subgroup of) an RSA group $\mathbb{Z}_{pq}$ where computing square roots is hard. They explicitly still want CDH to be hard in the group!