iterated discrete log problem Consider the following problem: given  $g_1 \ldots g_i,h_1 \ldots h_i  \in G$, $\forall i$ find  $x_i$ such that $g_i^{x_i}=h_i$ 

For $i=1$ this is the discrete log problem and  is assumed to to have some level of security based on the order of $G$ for certain groups. Let's call this security level $\lambda$. 

What happens to $\lambda$ as $i$ increases? Best case, it scales linearly with $i$. That is, its twice as hard to solve two DL instances in the same group $G$ as it is to solve one. Worse case, its no harder.

Im particularly curious with what happens when $G$ is a Schnorr group, though composite groups might work too. 

At least on a nieve quick glance, neither Pohlig–Hellman nor Baby-step Giant-step seem to benefit much from being run multiple times in the same group. I'm worried, however, that there are overlapping sub problems that if properly leveraged, perhaps using dynamic programing, would lead to a sub-linear scale up. The question is, how effective these techniques are.

I'd imagine someone has examined this before and I just need to find a paper on it, but as of yet I haven't found one. 

UPDATE
The Pollard Rho algorithm can apparently solve $i$ dl instances in the same group in $O{\sqrt{Ni}}$ where $N$ is the order of the group. So $\frac{1}{2}\lambda\sqrt{i}$.[1]

The real question appears to be  how index calculus methods handle it.
I don't know the general answer, however, it appears that Baby-step Giant-step is able to give you the solution in $O(\sqrt{in})$ time (where $n$ is the size of $G$); this is $O(\sqrt{i})$ times longer than it takes the same algorithm to solve a single discrete-log problem.

The first observation is that if you know the group order $n$ and a group generator $g$, that this problem can be reduced to $2i$ discrete log problems with the same base; if we find the values $y_a, z_a$ such that $g^{y_a} = g_a$, $g^{z_a} = h_a$, then we know $x_a = y_a^{-1} z_a \bmod n$.

So, here is how we can use Baby-Step/Giant-Step to solve all $2i$ discrete log problems in $O(\sqrt{in})$ time:


Let $t$ be the integer closest to $\sqrt{2in}$
Compute the $t$ values $g^j$, for $0 \le j &lt; t$, and store those values in a hash table.
For each $g_a, h_a$ value, compute the $n/t$ values $g_ag^{-tk}$ for $0 \le k &lt; n/t$.  Look up each value in the hash table; when we find $g_ag^{-tk} = g^j$, we know $g_a = g^{tk + j}$


The first step involves computing $t = O(\sqrt{in})$ values, and hence takes $O(\sqrt{in})$ time.  The second step involves iterating over $2i = O(i)$ variables, each iteration involving $n/t = O(\sqrt{n/i})$ time, for a total of $O(\sqrt{in})$ time.

Now, this gives an answer to the question from a theoretical standpoint ("yes, there do exist ways where we can take advantage of multiple subproblems"), however, it's not very interesting from a practical basis -- groups small enough for Baby-step/Giant-step to be a threat are too small to give real security.