Beyond Curve25519

[Daniel Kahn Gillmor]

On Thu 2015-01-15 15:53:33 -0500, Hanno Böck wrote:

> I find the search for "better than curve25119 curves" quite
> questionable.
>
> If you're really looking for something stronger you likely want
> something post-quantum. However the trouble with post quantum is that
> right now nobody really has any confidence in any of the algorithms.
> But people work on that, there's been some nice progress lately.
>
> Realistically: Nobody is every going to break 128 bit security level.
> When curve25519 breaks it'll very likely be because of quantum
> computers. But then e-521 will only provide very little extra
> security.

I'm not convinced by this argument.  It seems to assume that all
possible non-quantum mathematical advances in elliptic curve
cryptanalysis have already been published.

It's conceivable that there are other cryptanalysis techniques that are
known privately, or that will become known in the years before quantum
computers are actually feasible for real-world problems.  In those
scenarios, effective cryptanalysis will offer a work reduction beyond
the 128-bit security level, but we don't know how much.

It's also possible that quantum machinery becomes feasible for solving
problems of a certain size, but engineering constraints prohibit
constructing a machine with enough qubits to solve larger problems for
several more years.

In either scenario, having a larger curve with a higher security margin
gives a buffer against these currently-unknown attacks.

This is all tea-leaf reading, and seat-of-the-pants flights of fancy --
we don't actually know what the future will hold.  But it seems at least
plausible to me that some advance will be made that put 256-bit curves
into the "dubious" zone without entirely destroying elliptic curve
crypto.

And e-521 should still be far and away cheaper than rsa-2048 for secret
key operations, which are used widely today, while having a *much*
higher security margin.

       --dkg