# Hardness assumption: Extracting $g^y$ from $g^x, g^{x+y}$?

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$).

## 1 Answer

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$).
• 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. – tylo May 9 '17 at 9:45