[curves] Comparing high-speed / high-security curve implementations

[Diego Aranha]

Trevor,

This is probably too "researchy" and not ready for prime time, but we
recently implemented a GLS binary curve over GF(2^254) [1]  with the
following results for constant-time variable-base scalar multiplication:

Sandy Bridge: 115K
Haswell: 60K

Code was submitted to SUPERCOP and remains available at [2], but it's not
very readable at this time (multiple hands and lots of macros). I'm
currently porting it to RELIC. An implementation over curve K283 is coming
in a month or so, since Haswell has better support for binary fields than
prime fields, for the first time ever!

[1] http://eprint.iacr.org/2013/131.pdf
[2] http://sites.google.com/site/dfaranha/projects/gls254.tar.gz

--
Diego de Freitas Aranha
Institute of Computing - University of Campinas
http://www.ic.unicamp.br/~dfaranha


On Tue, Apr 22, 2014 at 8:32 PM, Trevor Perrin <trevp at trevp.net> wrote:

> Hi,
>
> I'm trying to understand the time/security ratio for modern ECDH
> implementations.
>
> Some cycle-counts are below, for the best ECDH implementations I'm
> aware of.  The numbers are for const-time variable-base scalar mult
> (the main component of ECDH) on two recent Intel microarchitectures.
>
> I've also provided a "normalized" time/security ratio in parentheses,
> which assumes that cycle-counts "should" scale as (security_level)^2.6
> due to Karatsuba, and sets "1" to the time/security ratio of Intel's
> recent P-256 implementation (smaller numbers are better).
>
> For curves with security level > 128, the best implementations I'm
> aware of are from Microsoft ([3], though code isn't available?) and
> Mike Hamburg [4,5].  I've listed the best-peforming of Microsoft's
> several curves.  Mike's curve appears to be the fastest, for its
> security level.
>
> Is there anything I'm missing that's competitive?  Anything coming soon?
>
>
> Sandy Bridge:
>
> [1] Intel P-256, 374K (1)
>
> [2] Curve25519, 194K (0.54)
>
> [3] Microsoft ed-382-mont, 590K (0.56)
>
> [4,5] Goldilocks-448, 688K (0.43)
>
>
> Haswell:
>
> [1] Intel P-256, 291K (1)
>
> [2] Curve25519, 162K (0.58)
>
> [4,5] Goldilocks-448, 571K (0.46)
>
>
> Trevor
>
>
> [1] http://eprint.iacr.org/2013/816.pdf
> [2] https://eprint.iacr.org/2014/134.pdf
> [3] http://research.microsoft.com/pubs/209303/curves.pdf
> [4] https://moderncrypto.org/mail-archive/curves/2014/000064.html
> [5] https://moderncrypto.org/mail-archive/curves/2014/000101.html
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20140423/d0698dd8/attachment.html>