The hardness of searching for small values in a cyclic group

Question

I was wondering if there are some hardness estimations for the following little problem:

Given a random $a$ from a cyclic group $\mathbb{G}_q$ how hard it is finding a value $x$ such that $a^{x} \bmod p < b$ for some fixed $b \in \mathbb{G}_q$. Say we deal with quadratic residues and $p$ and $q$ are both primes such that $p = 2q+1$.

On the one hand, the probability of finding such $x$ depends on the "space" of cyclic group values less than a certain number. On the other hand, as I recall, we don't know the exact distribution of values.

Do you know if there is something I can read about it?

Answer 1

This is like a conditional discrete logarithm problem.

Most likely you cannot do better than the usual improvements on discrete logarithms in generic groups (since you don't know the exact distribution of values and can only assume nearly uniform distribution unless there is a massive algebraic or combinatorial conspiracy) on average. But restricting to the smaller set will probably disrupt those methods.

There is a related unanswered question in crypto.stackexchange here. A comment there to the effect that (their bound is $b=p/k$) seems like it's worth pursuing.

This seems to reduce to a discrete logarithm problem in the multi-target setting, with a potentially very high target number depending on $k$. For a $k\approx \sqrt{p}$ index calculus seems like the best choice. Once you have one solution, getting more is relatively fast. Unsure if there's something better.