[curves] Improvements on discrete log for Koblitz curves?

[Diego Aranha]

Dear Trevor,

Thanks for mentioning this result!

My first reading does not indicate that the attack is restricted to Koblitz
curves, but applies to more general binary curves. Evidence for this can be
seen near the end of the paper, where impact is claimed over 4 FIPS curves
with n > 310 (supposedly, B/K-409 and B/K-571). Table 3 presents the
estimates and showcases the improvement. If I am reading this correctly, a
curve defined over 571-bit binary fields would give only ~186-bit security
under the new attack (instead of ~285 bits under generic Pollard's rho) and
a curve defined over a 409-bit binary field would give only ~166-bit
security (instead of ~204 bits). Moreover, the dominating stage of the
algorithm is easy to parallelize, presumably giving a close to linear
speedup in practice.

It's probably only a matter of time until this is applicable for curves at
lower security levels.
--
Diego Aranha


On Mon, Apr 6, 2015 at 9:45 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.)
>
>
> Trevor
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20150407/af62197f/attachment.html>