4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – SEJPM Oct 7 '18 at 18:21
  • $\begingroup$ Using pairings maybe? I'll try tomorrow morning $\endgroup$ – ddddavidee Oct 7 '18 at 19:36
  • $\begingroup$ As of 2014, none were known: crypto.stackexchange.com/questions/13034/… $\endgroup$ – rikhavshah Oct 7 '18 at 20:21
2
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.