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.

Improve this question
$\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, 2020 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$
    – ckamath
    Jul 7, 2020 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, 2020 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, 2020 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, 2020 at 15:55

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ That is pretty neat! $\endgroup$
    – ckamath
    Jul 22, 2020 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, 2020 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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