0
$\begingroup$

I am new in cryptography and I wonder whether there is any hardness assumption in cryptography where computation of $g^y$ is hard given $g^x, g^{x+y}$ ($g$ is group generator, $x$ is selected randomly while no restriction is on $y$).

$\endgroup$
8
$\begingroup$

No, this is (nearly) never hard.

To recover $g^y$ from $g^x,g^{x+y}$ all you need is a fast (ie polynomial-time) group operation (which is a given, because otherwise you'd have a hard time to come up with either value) and the ability to inverse fast (ie in polynomial time).

This follows from: $$g^y=g^{x+y-x}=g^{x+y}\cdot g^{-x}=g^{x+y}\cdot (g^x)^{-1}$$, where on the right you only have known values and fast operations and on the left you have your desired value.

Also note:

  • If you know the group order $q$, you can efficiently inverse as $a^{q-1}=a^{-1}$.
  • If you don't know the group order you likely still can invert quickly. For example you can still quickly find $a^{-1}\bmod n$ for composite $n$ (as is the case for RSA).
  • Inverting (finding $b$ such that $g^x\cdot b=1$) is not the same as computing the discrete logarithm (finding $b$ such that $g^b=X$).
| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ When the group structure supports the extended euclidean algorithm, it's anEuclidean domain. And if you construct finite structures as congruence classes and a ring homomorphism (such as $\mathbb{Z}_N$), the euclidean algorithm still works. But there are principle ideal domains, which are not euclidean domains. $\endgroup$ – tylo May 9 '17 at 9:45

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.