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

[Diego Aranha]

Trevor,

GLS stands for Galbraith-Linn-Scott and the binary curves were initially
studied at eprint 2008/334. This is the same technique used by Longa et al.
in their 4-dimensional scalar decomposition.

These implementations run in constant time, but the curves have
endomorphisms (like Koblitz curves) which make many researchers worried
about their actual security in practice, due to the additional structure.
An advantage is that generating curves for some of these families is
intrinsically rigid (in the SafeCurves sense). SECG supported curves with
endomorphisms (called "Koblitz prime curves" in the original document) and
one of them became the standard for Bitcoin's ECDSA. AFAIK, no important
speedup was ever found for the ECDLP with such parameters, and some authors
claim that binary Koblitz curves are actually more resistant to some
attacks (like approaches based on isogenies).

If you restrict the curves to an extremely conservative parameter choice,
then Curve25519 seems to be the clear winner.

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


On Wed, Apr 23, 2014 at 4:48 PM, Trevor Perrin <trevp at trevp.net> wrote:

> Thanks Diego, CodesInChaos,
>
> I've added those (and the DJB Kummer work) to my table.
>
> I'm not sure I'm comparing apples-to-apples anymore (GLS curves?
> "Lainey" curves (snowshoe)? Kummer surfaces?)  The speed of these
> things is impressive, but are there downsides?
>
> I was mainly interested in "extra-strength" curves like
> Goldilocks-448, E-521, and Curve41417, since I assumed the non-NIST,
> 128-bit security level was pretty much won for Curve25519/Ed25519.
> But maybe things are more interesting at 128-bits than I thought?
>
>
> 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)
>
> [6] Snowshoe-256, 132K (0.35)
>
> [7] Oliviera-256, 116K (0.31)
>
> [8] DJB-Kummer-256, 91.5K (0.24)
>
>
> Haswell:
>
> [1] Intel P-256, 291K (1)
>
> [2] Curve25519, 162K (0.58)
>
> [4,5] Goldilocks-448, 571K (0.46)
>
> [7] Oliviera-256, 60K (0.21)
>
> [8] DJB-Kummer-256, 91K (0.31)
>
>
> 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
> [6] https://github.com/catid/snowshoe
> [7] http://eprint.iacr.org/2013/131.pdf
> [8] http://cr.yp.to/hecdh/kummer-20140218.pdf
> _______________________________________________
> 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/7a2e856f/attachment.html>