Re: [Cfrg] On curves

On Wed, Jul 2, 2014 at 8:00 PM, Michael Hamburg <mike@shiftleft.org> wrote:
> Thanks for your perspective, Watson!
>
> But, how should we proceed?  We have, now, at least four pieces of code which aim for eventual production-grade Edwards curve crypto.  None of them entirely follows your suggestions:
>
> * Ed25519, which uses Edwards coordinates, p=5 mod 8, and an extra bit sign encoding;
>
> * Snowshoe, with endomorphisms over GF((2^127-1)^2), and I think no compression;
>
> * The Microsoft curves, which have code released for p = 2^(64b)-minimal, p=3 mod 4, and no point compression;
>
> * Ed448-Goldilocks, which uses a Solinas prime and a 1/sqrt(x) point representation.
>
> Are you requesting that the Microsoft folks release implementations of some of their other curves?

Yes, and I think we should change some choices. Adding point
compression with a separate sign bit is not that tricky, but I can't
remember when the patent expires. (I'm also not volunteering: my
timeframe for completion doesn't line up). Alternatively we decide
which of these is the closest to some reasonable ideal/doesn't offend
too many people.

Sincerely,
Watson Ladd
>
> Cheers,
> — Mike
>
> On Jul 2, 2014, at 10:37 PM, Watson Ladd <watsonbladd@gmail.com> wrote:
>
>> 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
>>
>> _______________________________________________
>> Cfrg mailing list
>> Cfrg@irtf.org
>> http://www.irtf.org/mailman/listinfo/cfrg
>

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin