<div dir="ltr">Dear Trevor,<br><br>Thanks for mentioning this result!<br><br>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.<div><br></div><div>It's probably only a matter of time until this is applicable for curves at lower security levels.</div><div>--</div><div>Diego Aranha</div><div><br></div></div><br><div class="gmail_quote">On Mon, Apr 6, 2015 at 9:45 PM Trevor Perrin <<a href="mailto:trevp@trevp.net">trevp@trevp.net</a>> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">An eprint paper claims an improvement over Pollard Rho vs the FIPS<br>
K-409 and K-571 curves:<br>
<br>
<a href="https://eprint.iacr.org/2015/310.pdf" target="_blank">https://eprint.iacr.org/2015/<u></u>310.pdf</a><br>
<br>
<br>
Seems like this might be building on the direction described below,<br>
from the "ellipticnews" blog:<br>
<br>
<a href="https://ellipticnews.wordpress.com/2012/05/16/two-new-papers-on-the-ecdlp-in-characteristic-2/" target="_blank">https://ellipticnews.<u></u>wordpress.com/2012/05/16/two-<u></u>new-papers-on-the-ecdlp-in-<u></u>characteristic-2/</a><br>
<br>
<br>
Anyone able to place the work in context?  (is this a real<br>
improvement?  by how much?  what are prospects for further advances,<br>
application to other curves, etc.)<br>
<br>
<br>
Trevor<br>
______________________________<u></u>_________________<br>
Curves mailing list<br>
<a href="mailto:Curves@moderncrypto.org" target="_blank">Curves@moderncrypto.org</a><br>
<a href="https://moderncrypto.org/mailman/listinfo/curves" target="_blank">https://moderncrypto.org/<u></u>mailman/listinfo/curves</a><br>
</blockquote></div>