[curves] Improvements on discrete log for Koblitz curves?

[Trevor Perrin]

Good summary of this, and some related work:

https://ellipticnews.wordpress.com/2015/04/13/elliptic-curve-discrete-logarithm-problem-in-characteristic-two/

Trevor


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.