11
$\begingroup$

Assume that $G$ is any cyclic group where the discrete log problem is hard, such as the elliptic curve group. Let $g$ be some generator of $G$.

The problem is as follows: Given $(g, g^x)$ for unknown $x$, output any pair of the form $(g^y, xy)$ for $y \neq 0$.

This seems awfully close to the discrete log problem but I could not find any reference for it, nor prove the equivalence myself.

Some things are clear: That algorithm cannot know $y$, since it cannot know $x$ (because the discrete log problem is hard). Also, the algorithm cannot use the same $y$ for different $x$, since that would also reveal $y$, and thereby, $x$.

For this case, we may assume that the Decision Diffie-Hellman problem in $G$ is hard. However, a hardness proof for non-DDH-hard groups will be nicer.

$\endgroup$
6
  • $\begingroup$ Came up in a protocol in discussion/development. Goal is to determine if this problem is really hard (by showing that if this is easy then dlog (or DDH) is easy). In the example DDH is hard but the general case is also interesting I presume. $\endgroup$ – Jus12 Jul 7 '20 at 20:28
  • 3
    $\begingroup$ Interesting question. It seems that if one can break this problem, then it is possible to "break" knowledge-of-exponent assumption (see KEA1 in this paper). This would mean that the problem lies between KEA and DLP. (Not sure how to formally argue this though as KEA is non-falsifiable and its definition involves an extractor.) $\endgroup$ – Occams_Trimmer Jul 7 '20 at 20:33
  • $\begingroup$ They must know the $y$ otherwise they cannot output $g^y$ then they know $x$. If they don't know $y$, then $xy$ is arbitrary which means $g^y$ is formed randomly. $\endgroup$ – kelalaka Jul 7 '20 at 20:35
  • 3
    $\begingroup$ @Occams_Trimmer Indeed KEA1 is trivially breakable if the above problem is easy. Hence, it does give some confidence. Thanks for the reference. $\endgroup$ – Jus12 Jul 7 '20 at 21:53
  • 1
    $\begingroup$ @kelalaka: given a CDH oracle, you can solve this problem (by selecting a random $xy$, computing $(g^x)^{(xy)^{-1}} = g^{y^{-1}}$ and then using the CDH oracle to derive $g^y$). Hence, it cannot be any harder than CDH $\endgroup$ – poncho Jul 22 '20 at 15:55
7
$\begingroup$

This problem is equivalent to the CDH problem:

Here is how to solve CDH given an Oracle that solves this problem:

  • Given $g, g^x$, we can compute $g^{x^{-1}}$ (which is equivalent to the CDH problem) by doing the following:

  • Call the Oracle with $g, g^x$; the Oracle gives us a pair $g^{y}, xy$

  • We compute $(g^{y})^{(xy)^{-1}} = g^{x^{-1}}$, hence showing one side of the equivalence

And, repeating my comment, here is how to solve this problem given a CDH Oracle:

  • Given $g, g^x$, we select an arbitrary value $z = xy$, and compute $(g^x)^{z^{-1}} = g^{y^{-1}}$.

  • We then invoke the CDH Oracle with $g, g^{y^{-1}}$ to recover the value $g^y$

  • We then return the values $g^y, z$, which shows the other side of the equivalence.

$\endgroup$
2
  • $\begingroup$ That is pretty neat! $\endgroup$ – Occams_Trimmer Jul 22 '20 at 21:33
  • $\begingroup$ Just a comment that CDH is equivalent to $g^{1/𝑥}$ only if the order of $g$ is known. If the order is hidden, such as $\phi(n)$ for some RSA modulus $n$ then a reduction is not known AFAIK. $\endgroup$ – Jus12 Jul 24 '20 at 11:50

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.