[Cfrg] On curves

[Watson Ladd <[e-mail]>]

Dear all,
After thinking about it for a bit, I've come up with the following
summary of my current position.

For compressed Edwards points, having p=3 (mod 4) is slightly easier
to explain how to deal with then p =5 (mod 8). We want to have the
same prime

There is no point to adding additional Weierstrass curves: additional
performance alone isn't that compelling unless implementors want to
implement a bunch of curves. Doing a good implementation is a bunch of
work, and in particular while a saturated word arithmetic is easy,
it's not worth doing unsaturated arithmetic unnecessarily.

Likewise the difference between 2^256 and 2^255 is minor in security,
but has a performance hit. so I would try to avoid going over word
boundaries.

As a result I suggest a Montgomery curve and isogenous twisted Edwards
curve with primes of the form p=2^(64*b-1)-c, c minimal so p is 3 (mod
4). I believe these have been computed by Longa et all.

However, at the 128 bit level, I see no technical arguments against
Curve25519. It's really a WG decision as how to do it.

This leaves the question of point representation: I would use Edwards
form with point compression: the Montgomery form has advantages in
variable-base multiplication, but it appears that summing the time of
one variable-base multiplication with one fixed-base multiplication
comes out lower for Edwards form. Again, for everything but signatures
the difference is probably minor.

Sincerely,
Watson Ladd