Discrete log hardness when secret is multiplied by public value

ManishB

7/8/24, 12:51 PM

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

1 + 2

discrete-logarithm

finite-field

kelalaka

7/8/24, 4:49 PM

Could you provide us with the source of this question?

ManishB

7/8/24, 9:36 PM

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.

Score:1

Crypto

poncho

7/8/24, 1:15 PM

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.

+ 1

ManishB

7/8/24, 9:36 PM

Thank you for your answer.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Discrete log hardness when secret is multiplied by public value

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.