Discrete log problem, when we have many examples 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:


Random choice. In this variation, the $a_i$'s are uniformly and independently distributed on $(\Z/p\Z)^*$.
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.
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&gt;1$ pairs $(a_i,b_i)$?  Of course, when $n=1$ this just reduces to the standard discrete log problem.  When $n&gt;1$, is this problem ever significantly easier than the basic discrete log problem?
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.