iterated discrete log problem

Question

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.

Answer 1

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

Answer 2

The answer to the final part of the question about index calculus depends on the finite field you are choosing to construct your group $G$.

If the characteristic is large enough, the algorithm to use is the number field sieve. In this case, computation of individual logarithms is much faster than the initial computation that leads to logarithm of the smoothness basis. As a consequence, we are almost in your worse case.

If the characteristic is small, the state of the art (at least asymptotically) is http://hal.inria.fr/hal-00835446. For this algorithm, the costly part is the descent phase, not the initial computation. Thus, the cost grows almost linearly with the number of logarithms.