What is this problem called and is it hard? given $g^x$ output ($g^y, xy$)

Question

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.

poncho · Answer

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.

What is this problem called and is it hard? given $g^x$ output ($g^y, xy$)

One Answer

Add your own answers!

Ask a Question