Probability that an attacker wins the discrete logarithm game when exponents are drawn from a subset Suppose $g$ is a generator of an order $p$ cyclic group in which discrete logarithm is hard and $p$ is a prime (i.e., given $g^x$ for a random $x \in \{0,1,\ldots, p-1\}$, it is hard to recover $x$ except with $negl(\lambda)$, where $negl(\lambda)$ is a negligible function of the security parameter $\lambda$).

My question is as follows: what happens if I am given $g^y$ such that $y$ is chosen randomly from $\{0, 1, \ldots, q-1\}$ for some $q &lt; p$, is there a way to quantify the hardness of discrete logarithm in terms of $q$? perhaps, something like: probability that one recovers $y$ is at most $\frac{1}{q} + negl(\lambda)$ and the probability is taken over the choice of $y$, or is there no way to quantify this?

I am mainly interested in knowing what happens in practice when one does this. For instance, in most libraries, the exponents are chosen to be 160 bits even though $p$ is 1024 bits.

(I posted this on math.stackexchange, but no responses. So, I am moving the question here by deleting it from there.)
Assume there exists an adversary for your q-subset DL problem that will be successful with probability $\mathsf{succ(\lambda)}$.
If you just use this adversary to attack the original DL problem, he will get an input that comes from the set it expects with probability $q/p$ and will therefore be succesfull with probability at least $q/p \cdot \mathsf{succ(\lambda)}$.
However we know that the DL problem is hard.
Thus, we can bound the success probability of the adversary:
$$\mathsf{negl}(\lambda) \ge q/p \cdot \mathsf{succ(\lambda)}$$
$$p/q\cdot\mathsf{negl}(\lambda) \ge \mathsf{succ(\lambda)}$$

Thus we get a bound for the success probability against your q-subset DL problem.

Whether this bound is helpful, depends on $q$. As long as $p/q$ is polynomial, the upper bound is still a negligible function. So at least in theory this is still a hard problem.

In practice and for a fixed group size that is of course a completely different story.

Of course, if $p/q$ is superpolynomial, then the all bets are off and this upper bound does not help you in any way.