Discrete log problem, when we have many examples

Question

Suppose I have many instances of the discrete log problem, all using the same unknown exponent. Is this problem easier than the standard discrete log problem?

Oh, heck, I should be more precise. Let $p$ be a large prime, chosen to be large enough that the discrete log problem modulo $p$ is (presumably) hard. Everything from here on will be in the multiplicative group of integers modulo $p$. Suppose we are given $a=(a_1,\dots,a_n)$ and $b=(b_1,\dots,b_n)$, where $b=a^k$, and we want to find $k$. In other words, $b_i = a_i^k$ for all $i$ (the same integer exponent for each of the $n$ instances), and we want to find the exponent $k$.

What is the hardness of finding $k$? Is it significantly easier to find $k$, given these $n$ instances, than it would be given only one instance? (say, is a greater than $n$-fold speedup available?)

$\newcommand{\Z}{\mathbb{Z}}$ I suspect it makes sense to focus in particular on three cases, depending upon how the $a$'s are chosen:

1. Random choice. In this variation, the $a_i$'s are uniformly and independently distributed on $(\Z/p\Z)^*$.

2. Non-adaptive adversarial choice. In this variation, the adversary chooses all of the $a_i$'s in advance, before seeing any of the $b_i$'s.

3. Adaptive adversarial choice. Finally, we can consider an adaptive variant, where the attacker chooses $a_1$, gets to see $b_1=a_1^k$, then the attacker can choose $a_2$, see $b_2=a_2^k$, and so on.

Does it help the adversary significantly to see $n>1$ pairs $(a_i,b_i)$? Of course, when $n=1$ this just reduces to the standard discrete log problem. When $n>1$, is this problem ever significantly easier than the basic discrete log problem?

Answer 1

On the third case, I have a comment. The third oracle may help the adversary using Cheon's algorithm for the DL problem.

Let $q$ be a prime order of the subgroup $\mathbb{G}$ of $(\mathbb{Z}/p\mathbb{Z})^{\times}$.

In the third case, the adversary has an oracle $a \mapsto a^k$ for any $a$. Hence, it can obtain $g^{k^i}$ from $g^{k^{i-1}}$ and so on. When $d \mid q-1$, Cheon's algorithm solves the augumented DL problem $(g,g^k,g^{k^d})$ over the group $\mathbb{G}$ of order $q$ with $O(\sqrt{q/d} + \sqrt{d})$ arithmetic computations. If there exists a divisor $d = O(q^{1/3})$ of $q-1$, the adversary can solve the DL problem with $O(\sqrt{q^{2/3}}+\sqrt{q^{1/3}}+q^{1/3}) = O(q^{1/3})$ arithmetic computations.

The third oracle enhances the adversary's power if the $O(\sqrt{q})$-time algorithm is the best attack for the DL problem.

Answer 2

In practice the view would be that no, it does not get any easier. Indeed many popular deployed schemes depend on it. For example the Trusted Authority in the Boneh-Franklin IBE scheme has a master secret s and issues private keys to users in the form s.ID_i, where ID_i is a point on an elliptic curve, and ID_i is related to the identity of the i-th user. It is a standard DL problem to find s from such a private key. Nevertheless the Boneh-Franklin scheme is assumed strong against a conspiracy of multiple users who can pool their secrets in an attempt to find the master secret s.

Answer 3

I can answer the question for the first of the three cases:

1. Random choice. In this case, seeing $n$ instances cannot help the adversary very much (not more than a $n$-fold speedup). The problem still remains hard, for suitably large $p$.

   Justification: By a simple reduction. Suppose we had a clever algorithm to solve the problem for $n>1$. I will show how to use that clever technique to solve the standard discrete log problem. Assume we are given $x,y$ with $y=x^k$ and we want to find $k$. Assume that $x$ is a generator. Then we pick random numbers $r_1,\dots,r_n$, set $a_i = x^{r_i}$, and set $b_i = y^{r_i}$. Then the entries $a_i$ are all uniformly and independently random, so this has the right distribution. Now we send $a=(a_1,\dots,a_n)$ and $b=(b_1,\dots,b_n)$ to our clever algorithm; by assumption it gives us back $k$, which solves the standard discrete log problem. So if the standard discrete log problem is hard, then the $n$-instance version must be hard too.

However I do not know what happens for the other two cases. The simple reduction above does not extend to those two cases.

(I can almost smell the hint of some relationship to the Diffie-Hellman problem. Maybe if DDH is hard then maybe we can apply similar techniques to show that $n$ instances can't help the adversary too much? I dunno.)