Probability that an attacker wins the discrete logarithm game when exponents are drawn from a subset

Question

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 < 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.)

Answer 1

The answer depends upon the factorization of $p-1$. Let me explain the situation for two example cases:

• Suppose $p-1=2p'$, where $p'$ is also prime. This is the best case (for the defender): it minimizes the information leakage. Then the best known attack that takes advantage of the reduced range of the exponents will solve the discrete logarithm in about $\sqrt{q/2}$ time. For instance, if $q$ is 160 bits, then the best attack known will take about $2^{80}$ time (assuming this is less than the time to solve the discrete logarithm modulo $p$ for an arbitrary exponent).

• Suppose $p-1=2p'p''$, where $p',p''$ are prime and $p'$ is pretty small and $p''$ is pretty big. This situation is bad for the defender and good for the attacker. An attacker can first recover the value of the exponent $y$ modulo $2p'$ in $\sqrt{p'}$ time (using Pohlig-Hellman). Then, the attacker can learn the full value of $y$ in $\sqrt{q/(2p')}$ time. The total running time will be $\sqrt{p'}+\sqrt{q/(2p')}$. If $p' \approx \sqrt{q}$, then the running time of the attack is $O(q^{1/4})$, which is significantly faster than the above -- yet the general discrete logarithm problem (for unrestricted exponents) might still be very hard.

What's going on here? Two things. First, if we know that the exponent comes from a consecutive range of $n$ possible values, then it's possible to recover the exponent in $\sqrt{n}$ time. Second, for any divisor $d$ of $p-1$, one can recover the value of the exponent $y$ modulo $d$ in $\sqrt{d}$ time (raise the group element to the $(p-1)/d$ power, then use Pohlig-Hellman to solve the resulting discrete log problem). You can combine both of these ideas. However, nobody knows how to do any better than that.

So, if you pick the parameters right, using an exponent from a restricted range can be secure. However, you have to pick them carefully. A good choice is to select $p$ so that $(p-1)/2$ is prime, and select $q$ to be at least 160 bits in length.

Even better yet, follow Paŭlo Ebermann's advice: select a prime $q$ that is 160 bits long or longer and a prime $p$ so that $q$ divides $p-1$, and then choose the generator $g$ to be a generator of the cyclic subgroup of order $q$ (e.g., let $g_0$ be a generator for the group of integers modulo $p$, then let $g=g_0^{(p-1)/q}$).

Answer 2

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.