<div dir="ltr"><div style="font-family:arial,sans-serif;font-size:13px">> Do you think 2x slower is accurate? (Or do you have performance<br>> numbers on Brainpool or similar curves I could add to the spreadsheet<br>
> [3])?<br>><br><br></div><span style="font-family:arial,sans-serif;font-size:13px">This is accurate for a modular multiplication:</span><div><font face="arial, sans-serif"><br></font><div><span style="font-family:arial,sans-serif;font-size:13px">- A generic random prime would require something like Montgomery reduction, which has quadratic complexity (but a little higher than the multiplication part, actually, due to a linear overhead).</span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px"><br></span></div><div><span style="font-family:arial,sans-serif;font-size:13px">- A special prime usually has faster reduction with linear complexity.</span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px"><br></span></div><div><span style="font-family:arial,sans-serif;font-size:13px">As a concrete example, our pairing code in Sandy Bridge had 60 cycles for the multiplication part and 100 cycles for the modular reduction at some point. If a special prime would give us a modular reduction in 10-20 cycles, the ratio would be approximately 2. </span><span style="font-family:arial,sans-serif;font-size:13px">Assuming that modular multiplication is the performance-critical operation for ECC, which should be the case for sane implementations, then the ratio is approximately 2. Notice however that additions are becoming significant in recent hardware due to faster integer multipliers (specially for pairing computation), but not enough to change this considerably.</span></div>
</div><div class="gmail_extra"><div><div dir="ltr">--<br>Diego de Freitas Aranha<br>Institute of Computing - University of Campinas<br><a href="http://www.ic.unicamp.br/~dfaranha" target="_blank">http://www.ic.unicamp.br/~dfaranha</a></div>
</div>
<br><br><div class="gmail_quote">On Tue, May 6, 2014 at 2:15 PM, Johannes Merkle <span dir="ltr"><<a href="mailto:johannes.merkle@secunet.com" target="_blank">johannes.merkle@secunet.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div><br>
> I do not think random primes are worth it. Looking at the past, the SNFS is not *that* great of an improvement. Of<br>
> course it matters in practice, and special >1024-bit numbers are factored whereas the best general result is RSA-768.<br>
> However, it (asymptotically) 'only' shaves around 20 bits of security off of RSA-2048 (~112-bit security), and 50 bits<br>
> off of RSA-15360 (~256-bit security).<br>
><br>
> Suppose there is indeed some similar speedup for prime-field elliptic curves, along with some index-calculus type<br>
> attack. Firstly, if the attack is subexponential, current sizes are dead regardless of the parameters. Secondly, as<br>
> Trevor mentions, how many extra bits in the prime field could we buy with the 2x slowdown of random primes? 64? 128? It<br>
> seems to me that a slightly bigger special prime would be a better tradeoff than a random one, all things considered.<br>
<br>
</div>Yes, the specific speed-up provided by the SNFS over the GNFS might compensate the increase in bit length suggested by<br>
Trevor. But I referred to the SNFS just to illustrate that special primes can in principle help to improve or to<br>
leverage attacks, i.e. it was a qualitative comparison, not a quantitative. Nobody knows if and how much a certain<br>
structure might help attacks, and extrapolations from finite field DL or integer factorization to ECDL are hardly possible.<br>
<br>
That said, let me make clear that I do not think that future attacks on special prime curves are at all likely to occur.<br>
Still, they are conceivable, at least for me.<br>
<div><br>
><br>
> There are also other kinds of structure to consider beyond the primes (which seem to presently be very low-risk). One<br>
> example of structure could be small even cofactors, which are known to speed up index calculus over extension fields in<br>
> some cases [1]. None of this affects elliptic curves over prime fields, but it still seems more realistic of a threat<br>
> than special primes.<br>
><br>
<br>
</div>I agree that this aspect should also be considered. However, I don't dare to assess which threat is more realistic.<br>
<br>
We should try to avoid any unnecessary structure for a conservative set of curves.<br>
<span><font color="#888888"><br>
<br>
--<br>
Johannes<br>
</font></span><div><div>_______________________________________________<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/mailman/listinfo/curves</a><br>
</div></div></blockquote></div><br></div></div>