On Mon, Apr 6, 2015 at 5:44 PM, Trevor Perrin <[email protected]> wrote: > An eprint paper claims an improvement over Pollard Rho vs the FIPS > K-409 and K-571 curves: > > https://eprint.iacr.org/2015/310.pdf > > > Seems like this might be building on the direction described below, > from the "ellipticnews" blog: > > https://ellipticnews.wordpress.com/2012/05/16/two-new-papers-on-the-ecdlp-in-characteristic-2/ > > > Anyone able to place the work in context? (is this a real > improvement? by how much? what are prospects for further advances, > application to other curves, etc.)
I'm much more skeptical than Aranha about this development. The paper does experiments with very small fields to argue heuristically for its runtime, but ignores the massive memory consumption and big constants. A processor that does useful work for the rho method can be squeezed into tens of thousands of gates, and can do many per second, but a processor for this is basically a computer, taking several seconds per relation found, and several gigs of ram. This may push the sizes that were broken up even higher. Of course, this is counterbalanced by the increased asymptotic performance of factor base methods, and there may be other tricks that can be used to accelerate this method. Odds are that detailed analysis will show that this is a real improvement, but I don't think we will ever see a calculation using it to find a discrete log without some very new ideas. Sincerely, Watson Ladd > > > Trevor > _______________________________________________ > Curves mailing list > [email protected] > https://moderncrypto.org/mailman/listinfo/curves -- "Man is born free, but everywhere he is in chains". --Rousseau. _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
