![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
ciphergothEDIT: have discovered why this isn't a good idea after all! It turns out that Pollard rho is much more optimized than I'd realized, and those optimizations mean that this isn't useful. In particular I was pointed to this on the cryptography mailing list. Basically it turns out they don't start from scratch every time when they generate ax + by — they just update the original point with a single point addition chosen by a hash function. So basically t_a == t_p and there's no advantage to the below.
Either this isn't original, or it doesn't work, or I've found a way to solve the discrete logarithm problem on elliptic curves a little bit faster. This idea woke me up this morning so I'm keen to know which :-)
The standard algorithm is "Pollard rho": Supposing you're looking for an x such that xg = y where g, y are in some group G. You generate lots of random a, b st 0 <= a, b < |G|, and look for a collision in ag + by: in other words a pair such that ag + by = a'g + b'y. Then you have a + bx = a' + b'x (mod |G|) and so you solve for x in (a - a') = (b' - b)x (mod |G|). By the standard birthday argument, you need to generate around sqrt(2*ln(2)*|G|) values of ag + by for a 50% probability of success; if generating such a pair takes time t_p then the whole thing takes time roughly sqrt(2*ln(2)*|G|) t_p.
The idea behind my speedup is to reduce the size of the space you're looking for a collision. Suppose that given a point p, you can find the point p + g in time t_a. Find a way to efficiently distinguish a subset D of points in the curve, where |D| should be around |G|(t_a / t_p); this can be as simple as hashing the point and checking if the k least significant bits are zero for some suitable k. Now, after generating ag + by, find the least non-negative integer c such that (a + c)g + by is in D; you do this just by starting with ag + by, and adding g repeatedly until you get a point in D. It's this value we look for collisions in. When we find a collision, we have (a + c)g + by = (a' + c')g = b'y, so we solve (a + c - a' - c') = (b' - b)x (mod |G|) to find x.
Now generating points is slower; instead of taking time t_p, it takes on average t_p + (|G|/|D|)t_a. But we now only need to generate sqrt(2*ln(2)*|D|) points for a 50% success probability, so this takes time in total sqrt(2*ln(2)*|D|)(t_p + (|G|/|D|)t_a). Since |D| ≅ |G|(t_a / t_p), this is ≅ 2 sqrt(2*ln(2)*|D|)t_p, and so the speedup is roughly sqrt(t_p / t_a)/2. So how much faster this is depends roughly on how many point additions it takes to find ag + by.
The current world record in ECDL was in a 112-bit curve. With the most naive possible algorithm for calculating ag + by, we'd see t_p/t_a of around 672, meaning that this technique would speed things up by a factor of 13 or so. However, doing lots of precomputation on g and y would allow a much faster table-driven implementation to get t_p/t_a to as little as 13 - but even then, this technique would nearly halve execution time, and it gets better as the curve gets larger.
This trick seems much too simple not to have been thought of before, but if so I don't know why the world record attack didn't use it. Does this make sense? If so, does it work? If so, is it original? Thanks!
Either this isn't original, or it doesn't work, or I've found a way to solve the discrete logarithm problem on elliptic curves a little bit faster. This idea woke me up this morning so I'm keen to know which :-)
The standard algorithm is "Pollard rho": Supposing you're looking for an x such that xg = y where g, y are in some group G. You generate lots of random a, b st 0 <= a, b < |G|, and look for a collision in ag + by: in other words a pair such that ag + by = a'g + b'y. Then you have a + bx = a' + b'x (mod |G|) and so you solve for x in (a - a') = (b' - b)x (mod |G|). By the standard birthday argument, you need to generate around sqrt(2*ln(2)*|G|) values of ag + by for a 50% probability of success; if generating such a pair takes time t_p then the whole thing takes time roughly sqrt(2*ln(2)*|G|) t_p.
The idea behind my speedup is to reduce the size of the space you're looking for a collision. Suppose that given a point p, you can find the point p + g in time t_a. Find a way to efficiently distinguish a subset D of points in the curve, where |D| should be around |G|(t_a / t_p); this can be as simple as hashing the point and checking if the k least significant bits are zero for some suitable k. Now, after generating ag + by, find the least non-negative integer c such that (a + c)g + by is in D; you do this just by starting with ag + by, and adding g repeatedly until you get a point in D. It's this value we look for collisions in. When we find a collision, we have (a + c)g + by = (a' + c')g = b'y, so we solve (a + c - a' - c') = (b' - b)x (mod |G|) to find x.
Now generating points is slower; instead of taking time t_p, it takes on average t_p + (|G|/|D|)t_a. But we now only need to generate sqrt(2*ln(2)*|D|) points for a 50% success probability, so this takes time in total sqrt(2*ln(2)*|D|)(t_p + (|G|/|D|)t_a). Since |D| ≅ |G|(t_a / t_p), this is ≅ 2 sqrt(2*ln(2)*|D|)t_p, and so the speedup is roughly sqrt(t_p / t_a)/2. So how much faster this is depends roughly on how many point additions it takes to find ag + by.
The current world record in ECDL was in a 112-bit curve. With the most naive possible algorithm for calculating ag + by, we'd see t_p/t_a of around 672, meaning that this technique would speed things up by a factor of 13 or so. However, doing lots of precomputation on g and y would allow a much faster table-driven implementation to get t_p/t_a to as little as 13 - but even then, this technique would nearly halve execution time, and it gets better as the curve gets larger.
This trick seems much too simple not to have been thought of before, but if so I don't know why the world record attack didn't use it. Does this make sense? If so, does it work? If so, is it original? Thanks!
