What Is The Definition Of The J-invariant Of An Elliptic Curve?

What are the advantages of elliptic curve cryptography using binary fields over prime fields and vice versa?

• Basically, for elliptic curve cryptography purposes, what are the advantages of using elliptic curves which are defined over a binary field over the elliptic curves which are defined over a prime field and vice-versa, in terms of performance(speed) and security? Also, what references would you suggest which describe how to speed up the implementation of ECC over these curves?

• Answer:

  Security: There are no known attacks that greatly weaken either class of curves.  However, there is some concern about binary curves because of the recent improvements in attacking discrete logarithms over small-characteristic fields.  These attacks don't yet matter for elliptic curves unless you have a pairing.  So don't use pairings on small-characteristic fields.  But it might be worth going with a prime-field curve for long-term security. Speed: Binary curves are smaller and faster in hardware than prime-field ones.  This is because they have shorter formulas, and because binary operations have no carries, and because binary squaring is very cheap (it's linear).  A recent binary curve implementation paper can be found at https://eprint.iacr.org/2013/131.pdf. Prime-field curves are usually faster on general-purpose CPUs, because those CPUs usually have a giant integer multiplier circuit, and they don't usually have a giant binary multiplier circuit.  However, as the above paper shows, Intel's PCLMULQDQ gives access to a giant binary multiplier (especially on Haswell) and can move things in favor of binary curves. The fastest prime-field curves these days are Edwards curves.  See, for example, http://www.iacr.org/archive/asiacrypt2008/53500329/53500329.pdf.  The downside of Edwards curves is that they're slightly special (they have cofactors divisible by 4).  For example, the NIST curves cannot be put in Edwards form. Either sort of curve can have its speed improved by using fancy shapes (Edwards, Lambda, etc) and, for certain curves, endomorphisms.  See, for example, https://eprint.iacr.org/2011/608.pdf. Edit: suggested that I mention Montgomery curves.  These are a very simple, fast curve shape that's mainly suitable for Elliptic Curve Diffie Hellman.  They're equivalent (isomorphic and isogenous) to Edwards curves, so you can use the Montgomery form of a given curve for ECDH and the Edwards form for other protocols that don't work well in Montgomery form.  Compared to Edwards form, Montgomery form is about as fast and much simpler for ECDH, slower for keygen, and both slower and more complicated for other situations.  The most popular Montgomery curve is http://cr.yp.to/ecdh.html. Another edit at the same time: the cofactor of 4 can be removed by various means to create a prime-order group, so this is only a small downside.  But there still isn't a profitable way to write the NIST curves in Edwards form. A third edit: The fastest keygen algorithm I know is the "signed all bits set combs" algorithm.  It is described in my paper at https://eprint.iacr.org/2012/309. Intellectual property: Elliptic curves are still somewhat IP-encumbered.  For example, the point compression patent is probably expiring this July.  It is my impression that binary elliptic curves are more encumbered than prime-field ones.  This is because Certicom put a lot of work into them in the '90s, and patented everything.  (They patented prime-field stuff too, but more of that was known already.)  I could be mistaken about this, though, as I haven't researched it recently.