Logjam on Elliptic Curves? I think we're all aware of the Logjam attack.

From now on we know that re-using primes for DH is a bad idea.

But we also say that elliptic curves are safe from the attack (relying on the NFS), because it cannot be applied. I understand this.

Now in my mind this question arose:

Assuming we had enough computational power (maybe using ASICs) is there a similar pre-computation attack on ECDH?

And if it is possible, how high would the gains be?Could one reduce the workload per connection to a modest value ($\approx 2^{20}$), while still not needing to maintain a gigantic table ($&gt;2^{60}$ storage)?It would already suffice if such an attack would work on secp256....
Let's recall how discrete logarithms are solved in strong elliptic curve groups. The basic idea is to iteratively walk through many combinations of the form $x_i = a_iP + b_iQ$ until we find a distinguished one, i.e., one that shares some common property (like the lowest $k$ bits of $x_i$ set to 0). We accumulate enough distinguished points until we find a collision.

When we find two distinct pairs $(a_1, b_1)$, $(a_2, b_2)$ that evaluate to the same value $x_1 = x_2$, we recover the logarithm by finding $Q = dP = \frac{a_2 - a_1}{b_1 - b_2}P$, which follows from $a_1P + b_1Q$ $=$ $a_2P + b_2Q$. We expect this to happen after $\sqrt{\pi n / 2}$ elliptic curve group operations.

Since by the time we get to the second discrete log we already know the first one, we can reuse the distinguished points found during that log computation. This slightly increases the chances of finding a collision. Suppose we have a hit $a_1P + b_1Q_1$ $=$ $a_2P + b_2Q_2$, where $Q_1$ was the first discrete logarithm target, and $Q_2$ is the current one. Rewrite this as $(a_1 + b_1d_1)P$ $=$ $a_2P + b_2Q_2$, where $d_1$ is the first discrete logarithm. Now we have $d_2 = \frac{a_1 - a_2 + b_1d_1}{b_2}$.

This accelerates the second logarithm by a factor of $2$, the third one by a factor of $8/3$, and the $i$th one by a factor $\approx \sqrt{i}$ compared to if they were solved independently. So as you see, the benefits of precomputation exist, but are much more limited than in the number field sieve case.