> I do not think random primes are worth it. Looking at the past, the SNFS is > not *that* great of an improvement. Of > course it matters in practice, and special >1024-bit numbers are factored > whereas the best general result is RSA-768. > However, it (asymptotically) 'only' shaves around 20 bits of security off of > RSA-2048 (~112-bit security), and 50 bits > off of RSA-15360 (~256-bit security). > > Suppose there is indeed some similar speedup for prime-field elliptic curves, > along with some index-calculus type > attack. Firstly, if the attack is subexponential, current sizes are dead > regardless of the parameters. Secondly, as > Trevor mentions, how many extra bits in the prime field could we buy with the > 2x slowdown of random primes? 64? 128? It > seems to me that a slightly bigger special prime would be a better tradeoff > than a random one, all things considered.
Yes, the specific speed-up provided by the SNFS over the GNFS might compensate the increase in bit length suggested by Trevor. But I referred to the SNFS just to illustrate that special primes can in principle help to improve or to leverage attacks, i.e. it was a qualitative comparison, not a quantitative. Nobody knows if and how much a certain structure might help attacks, and extrapolations from finite field DL or integer factorization to ECDL are hardly possible. That said, let me make clear that I do not think that future attacks on special prime curves are at all likely to occur. Still, they are conceivable, at least for me. > > There are also other kinds of structure to consider beyond the primes (which > seem to presently be very low-risk). One > example of structure could be small even cofactors, which are known to speed > up index calculus over extension fields in > some cases [1]. None of this affects elliptic curves over prime fields, but > it still seems more realistic of a threat > than special primes. > I agree that this aspect should also be considered. However, I don't dare to assess which threat is more realistic. We should try to avoid any unnecessary structure for a conservative set of curves. -- Johannes _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
