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

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$$.

• And yes, I did perform a (admittedly quick) search over the site and via google and yes I do realize that for DDH / CDH (instead of CDH / DLog) the answer is "yes". Also I do know that apparently there are groups where CDH and DLog are equivalent. – SEJPM Oct 7 '18 at 18:21
• Using pairings maybe? I'll try tomorrow morning – ddddavidee Oct 7 '18 at 19:36
• As of 2014, none were known: crypto.stackexchange.com/questions/13034/… – rikhavshah Oct 7 '18 at 20:21

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).
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!