[curves] Improvements on discrete log for Koblitz curves?

[Watson Ladd]

On Mon, Apr 6, 2015 at 5:44 PM, Trevor Perrin <trevp at trevp.net> 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
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves



-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.