[curves] Choosing an extra-strength curve

[Trevor Perrin]

On Tue, May 6, 2014 at 9:57 AM, Johannes Merkle
<johannes.merkle at secunet.com> wrote:
>
> IMHO it is wise to have fast curves for applications that need high performance, but to also have, as a backup,
> conservatively chosen curves which avoid simplifying structures. This second class of curves may be considerably slower,
> but there are plenty of application scenarios where the crypto speed doesn't really matter. Hey, most TLS servers prefer
> RSA encryption cipher suites with 2048 bit, this is much slower than most Brainpool curves.

I guess it depends on how many new curves we get.

If we get 3, maybe you'd agree with Mike's "desert island" choices? [1]:
 - Curve25519/Ed25519
 - "bigger fast field" such as Goldilocks (~3.5x the time of
Curve25519, ~96 bits more security)
 - "pseudorandom curve over a pseudorandom 512-bit field, 12-16x time
of Curve25519

My guess is implementors won't adopt more than 1 or 2.  It's a lot of
work to implement / test / optimize a curve, and ship code and lookup
tables for it.  And too many options confuses people and hurts
compatibility.

So I think we get curve25519/ed25519 and *maybe* one more, if it's
fast enough to be used widely.  I think Goldilocks or similar would
fit the bill, but an "ultra-conservative" choice risks being too slow
for a lot of cases, thus not making it into libraries / HW and
becoming ignored.

I also think it's questionable whether an "ultra-conservative" curve
is the right way to purchase extra security margin.  William Whyte has
argued for using multiple public-key algorithms in parallel [2], and
if we're going to spend exorbitant amounts of time for security
margin, that may make more sense, particularly with post-quantum
algorithms (e.g. NTRUEncrypt, McEliece/McBits etc).


Trevor


[1] http://www.ietf.org/mail-archive/web/cfrg/current/msg03961.html
[2] http://blog.securityinnovation.com/blog/2013/08/king-rsa-cryptos-successor-why-we-need-to-move-away-from-a-monarchy.html