Let $g$ be a group generator of prime order $q$. Suppose we are given two elements $g^y$ and $x_1$. Can we find out if $y=x_1+x_2$ for some $x_2$?

Thanks

-

## closed as unclear what you're asking by figlesquidge, e-sushi, AFS, Maeher, GillesFeb 20 '14 at 13:36

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

If $y$ is an integer, and $x_1$ is a group element, how does $y - x_1 = x_2$ make sense? Are you assuming a specific group representation (so you can map between integers and group elements)? Are, if you compute $y - x_1$ either in the integers or within the group, won't such an $x_2$ always exist? – poncho Feb 18 '14 at 14:20
As poncho says, your question doesn't make sense as currently written. As such I feel I have to downvote and close-vote, but as soon as you sort it out I'd be very happy to reverse the vote :) – figlesquidge Feb 18 '14 at 14:31
I recommend using uppercase letters for group elements and lower case letters for scalars. That way you easily see that you're adding a scalar an a group element which doesn't make much sense. – CodesInChaos Feb 18 '14 at 17:14

I hope you understand your question.

Your question is that given generator $g$ of a prime order $q$ group and some element $g^y$ of that group and another element $x_1 \in Z_q$ you want to check if there is such an $x_2$ or find $x_2\in Z_q$ such that $y\equiv x_1+x_2 \pmod q$? I assume that in this setting the discrete logarithm problem is hard, right?

Firstly, for every $y\in Z_q$ you will find a decomposition in $x_1$ and $x_2$ such that $y\equiv x_1+x_2 \pmod q$. Your value will just be $x_2\equiv y-x_1 \pmod q$. So, yes this is always true.

Secondly, can we efficiently find such $x_2$? If there would be an efficient way to do so, then given $(q,g,g^y)$, take an arbitrary $x_1 \in Z_q$ which will be an instance to your problem. Since we know there is an $x_2$ in any case, figure out $x_2$ and output $y\equiv x_1 +x_2 \pmod q$, which is a solution to the discrete logarithm problem. So if the discrete logarithm problem is hard, figuring out $x_2$ is hard (as otherwise this algorithm would provide an efficient reduction to the discrete logarithm problem).

-