I can answer the question for the first of the three cases:
- 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$.
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.
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.)
