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$).
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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$).
-
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$– tyloMay 9, 2017 at 9:45