[curves] FourQ

[Michael Hamburg]

Nice.  It’s what, 20% faster than before?

My impression had been that GF((2^127-1)^2) has somewhat slower field multiplication than the fastest GF(p) at the same level (eg Montgomery-friendly primes), and makes up for it in faster inversion.  But crunching the numbers, it looks like MSR’s latest code has about as fast field arithmetic as any GF(p), at least on the processors they measured, and of course still much faster inversion.  (I have no idea how the comparison would turn out on ARM or Broadwell, having not studied that field very carefully).  It looks like they’re using a btr+adc lazy reduction and it turns out to be very efficient.

Cheers,
— Mike


> On Sep 13, 2015, at 12:33 AM, Trevor Perrin <trevp at trevp.net> wrote:
> 
> There's an updated paper and new code for MSR's FourQ curve:
> 
> http://eprint.iacr.org/2015/565
> 
> http://research.microsoft.com/en-us/projects/fourqlib/
> 
> I tossed the numbers into the spreadsheet at [1], but the paper has a
> better performance analysis across several platforms.
> 
> What do people think?
> 
> Without using the endomorphisms the performance is better than 25519,
> and then endomorphisms are close to a 2x speedup.  And if unencumbered
> use of the endomorphisms is just ~4 years away [2], that's not that
> long, in the scheme of things.
> 
> 
> Trevor
> 
> [1] https://docs.google.com/spreadsheets/d/1SO3NGX-EgIZ1slw9uExb5FoeFy5TVkuA2lEutP6roYI/edit#gid=0
> 
> [2] https://moderncrypto.org/mail-archive/curves/2014/000133.html
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves