# Is there a method to break an EC curve for all key-pairs (Q,d) such that (Q=d*G) faster than breaking every single key-pair?

Related to this question: Is there any memory trade-off that helps such attack?

Obviously if the field size is very small (say 40 bits) it´s possible, but what if the field size is 160 bits long? or 256 bits?

-
I'm having a bit of trouble parsing your question. By 'breaking an EC curve for all key-pairs', what do you mean? If you mean putting together an explicit table for all possible d's and Q's, well, that's obviously infeasible for a 160-bit curve (as the table itself will have circa $2^{160}$ entries). If that's not what you mean, well, what do you mean? –  poncho Sep 12 '12 at 13:23
Suppose that, in a 160-bit curve, you could use 2^90 time/space to find a trapdoor so, afterwards, you can find any discrete log in O(1). Is that possible? –  SDL Sep 12 '12 at 16:00
I've read baby-step giant-step algorithm for solving the discrete log and it uses a pre-computed table that can be reused to break following keys, but I don't know how the cost of building the table relates to the total cost of the algorithm. If building the table is 99% of the required time, then one can break 100 keys at the price of one. I don't see how Pollard's rho algorithm for logarithms can be optimized to break many key-pairs at the price of one. –  SDL Sep 12 '12 at 16:00

Well, Big-Step/Little-Step can be written as a precompute-table and then lookup type algorithm, however, it doesn't become close to practical with a 160 bit field.

Here's how Big-Step/Little-Step works; we first select two integers $a$ and $b$ with $ab \ge size(group)$ (I consistently talk about group rather than the curve; that's because Big-Step/Little-Step will apply to any finite group. In terms of Elliptic Curves, for practical purposes we can make the assumption that $size(group) \approx size(field)$.

In the precompute phase, we construct a table with the pair of values $(ib, (ib)G)$ for $(0 \le i < a)$. This table will contain $a$ rows, and takes $O(a)$ time to construct. Note that this table does not depend on the point $Q$ that we'll end up computing the discrete log on.

In the lookup phase, we compute the points $Q - jG$ for $0 \le j < b$, and look up each of these points in the table. If we find one of the points in the table, we have $(ib)G = Q - jG$ (where $i$ is the value in the table, and $j$ is the value we used to compute the point), we then know that $Q = (ib + j)G$, and hence we have the discrete log. This phase takes $O(b)$ expected time (assuming each lookup can be done in constant time using appropriate data structures).

Now, the total time taken is $O(max(a,b))$; to minimize this value, we generally assume that $a=b\approx\sqrt{size(group)}$, thus giving us a squareroot time algorithm. However, there is no such hard requirement, and if we're going to reuse the table multiple times, it makes sense to increase the value of $a$ (the one time cost) so we can decrease $b$ (the per-discrete-log cost).

However, once we start talking about a group with circa $2^{160}$ members, well, this doesn't work out. For one, even in the balanced case, we're talking about a table with $2^{80}$ entries; that in itself is impractically large. If we consider increasing $a$, the table size becomes even more impractically large.

Now, one obvious idea to reduce the table size is to create a Rainbow table. It turns out that Rainbow tables will work in the way we want (allowing us to build a table that we can use to lookup $i$ given $(ib)G$ values); however, it turns out not to buy us anything. Rainbow tables allow us to compress the table by a factor of $k$ by increasing the lookup time by that same factor $k$. That turns out to be the killer; because the lookup phase involved $O(b)$ table lookups. We can make the table $O(a/k)$ entries long; however the lookup phase will now take $O(kb)$ work; we haven't gained anything that we wouldn't have gotten by making $a$ smaller by a factor of $k$ and $b$ larger by a factor of $k$.

-
Great answer.That leaves Big-Step/Little-Step out of the question. Does Pollard's rho algorithm offer any trade off? It there any way one can find a trapdoor (e.g. isomorphism with some other field) so that the DLOG problem becomes easier? –  SDL Sep 12 '12 at 19:05
The problem with this is that you're assuming separate pre-calculation and lookup phases. A single phase multi-target attack is an important scenario too, where you simply want to crack one of a million known public keys. I believe the gain in that scenario is still rather small, but it exists. –  CodesInChaos Sep 13 '12 at 15:01
@CodesInChaos: actually, that is not an obscure scenario. Even if you are attacking one ECDSA key, if you have a million signatures with that key, all you need to do is solve one Discrete Log problem with any of the $r$ values in any signature, then you can recover the private key (!). That being said, do you have any algorithm that provides any gain (however small) over the known sqrt time algorithms; that would imply that ECDSA could be broken faster than currently believed. –  poncho Sep 13 '12 at 15:24
@CodesInChaos: a proof that the 'given a million DL problems, solve any one' problem isn't any easier than solving a single DL problem. Suppose we had an oracle that could solve the million DL problem; then, to solve a DL problem for point $X$, we generate a million random $r_i$ values and give the oracle the million values ${r_i X}$; if it gives us two values $k, j$ with ${k G = r_j X}$, then we can compute the discrete log of X as $k r_j^{-1} G = X$ –  poncho Sep 13 '12 at 20:27