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

[Trevor Perrin]

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