8
$\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$
4
  • 2
    $\begingroup$ AFAIK there are no know groups where this is the case, but we know no proof that shows they don't exist either. $\endgroup$ Jan 20 '14 at 14:23
  • $\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
7
$\begingroup$

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.

$\endgroup$
4
$\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.