Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?


share|improve this question

closed as unclear what you're asking by figlesquidge, e-sushi, AFS, Maeher, Gilles Feb 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).

share|improve this answer

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