[curves] Microsoft ECCLib for "NUMS" curves

[Michael Hamburg]

On Jul 4, 2014, at 3:52 AM, Trevor Perrin <trevp at trevp.net> wrote:

> On Thu, Jul 3, 2014 at 8:13 AM, Michael Hamburg <mike at shiftleft.org> wrote:
>> 
>> On Jul 3, 2014, at 2:38 AM, Trevor Perrin <trevp at trevp.net> wrote:
>> 
>>> To answer my own question: the observed difference is probably mostly
>>> "nurture".  Microsoft's 256-bit Edwards curve is similar to Curve25519
>>> so could probably be optimized to about the same speed:
>>> 
>>> - Microsoft's field prime is 2^256 - 189 instead of 2^255 - 19.
>>> Seems pretty similar.  Is there any inherent efficiency difference for
>>> scalar multiplication?
>> 
>> Microsoft’s numbers with Mers 256 vs 255 suggest that the “nature” difference
>> on this is about 5%,
> 
> I know that's a rough number, but I'm curious how you arrived at it.
> 
> In [1] and [2] Microsoft quotes:
> 
> ed-256-mers (2^256 - 189) => 234 Kcycles
> ed-255-mers (2^255 - 765) => 226 Kcyles
> 
> Adjusting for the extra half-bit of security at 256, ed-255-mers only
> looks ~2.5% more efficient.  Assuming that Microsoft implemented these
> similarly (which is a guess because they haven't released
> ed-255-mers), could we roughly attribute that 2.5% to using a 255 bit
> field instead of 256?

I was measuring merely speed, and not efficiency scaled for bit length.

> Curve25519 has prime closer to 2^255 (-19 versus -765), so I guess
> you're estimating additional benefit from that?
> 
> To be fair we should account for 2^255-19 being 5 mod 8, whereas
> Microsoft's curves have 3 mod 4 primes.  So point decompression during
> signature validation might include a couple extra field operations.
> But I think this should be well less than 1% of signature verification
> cost (?), so I guess you're assuming the benefits of small constant
> (19) outweigh the added cost of 5 mod 8?

2^255-19 is faster than Microsoft’s 255-mers due to a combination of a
small constant, the 255 instead of 256, and many years of implementations.

>>> - Microsoft's field prime is 3 mod 4 instead of 5 mod 8.  AIUI,
>>> calculating square roots (e.g. point decompression) for 5 mod 8 has a
>>> 50% chance of needing a small extra step (a field multiplication by
>>> the constant sqrt(-1)).  Could anyone summarize the significance of
>>> this?  If the curves are mostly the same otherwise, is this a reason
>>> to switch?
>> 
>> It’s not a big deal, and in my opinion it isn’t a reason to switch.  It’s slightly more
>> annoying, and it makes some other things not work as well (can’t use choose
>> principal square root).
> 
> Could you expand on that?  What other things don't work as well?
> What's a "principal square root"?
> 
> Trevor
> 
> [1] http://eprint.iacr.org/2014/130.pdf
> [2] http://patricklonga.webs.com/Presentation_CFRG_Selecting_Elliptic_Curves_for_Cryptography.pdf


In a 3 mod 4 field, one of the roots is always square and the other is not.  The square one is “principal”, and it’s a power of the input point.  It’s a nice way to specify square roots.  The squaring map is also 1:1 on values which are already square, which is sometimes useful in Elligator-style constructions.

A related feature is that one can use Legendre symbol instead of high bit or low bit to define the sign of a number.  Since the Legendre symbol is algebraic, it propagates through formulas in nicer ways.

The downside of 3 mod 4 is that you need to use isogenies to switch between straight and twisted Edwards curves, instead of isomorphisms, and also that you’re excluding attractive primes like 2^255 - 19.

— Mike