2
$\begingroup$

Given y = g ^ x is discrete log hard on some finite field, is y = g ^ (kx) also equally secure if the value k is a publicly known value which was randomly selected from a uniform distribution ?

To my understanding, if k and x are independent and chosen randomly, then the security of the discrete logarithm problem is not significantly affected as an attacker still needs to compute the discrete logarithm of y with respect to the base g, and the knowledge of k does not provide any useful information for solving the problem.

Still if there is something I'm missing, please point out. Thanks

$\endgroup$
2
  • $\begingroup$ Could you provide us with the source of this question? $\endgroup$
    – kelalaka
    Commented Jul 8, 2023 at 16:49
  • $\begingroup$ I was studying Sigma Protocol and this thought randomly popped in my mind: whether the domain of possible values for secrets would be smaller if the secret is a multiple of known value. But being a finite field of prime order that wouldn't be the case. So I wondered if there was anything else. $\endgroup$
    – ManishB
    Commented Jul 8, 2023 at 21:36

1 Answer 1

1
$\begingroup$

is $y = g ^ {kx}$ also equally secure if the value $k$ is a publicly known value which was randomly selected from a uniform distribution ?

Here is a clearer way to look at it: suppose we have an oracle that, given $k, y=g^{kx}$, is able to recover $x$.

Then, given $g^x$, we can randomly select $k$, compute $(g^x)^k = g^{kx}$. We can then give $k$ and $y = g^{kx}$ to our Oracle (and note that the precondition that $k$ must be randomly chosen is met), which will then give us $x$, solving the discrete log problem.

Hence, your problem cannot be any easier then the standard discrete log problem, because if we can solve it, then we can solve the discrete log problem.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. $\endgroup$
    – ManishB
    Commented Jul 8, 2023 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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