[curves] Improvements on discrete log for Koblitz curves?

Trevor Perrin trevp at trevp.net
Sun Apr 12 23:45:48 PDT 2015

Good summary of this, and some related work:



On Tue, Apr 7, 2015 at 6:08 PM, Watson Ladd <watsonbladd at gmail.com> wrote:
> 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.

More information about the Curves mailing list