Complete group laws for prime-order elliptic curves: a step towards safer implementations of standard curves

Eurocrypt 2016 didn’t feature many papers directly relevant to curve-based cryptography, but one presentation stood out: Joost Renes presented his work with Craig Costello and Lejla Batina on complete addition laws for prime-order elliptic curves.

From a cryptographic point of view, complete addition laws are important for designing and implementing uniform and constant-time algorithms on elliptic curves. The most well-known and successful example of this is the (twisted) Edwards model for elliptic curves, where a single formula can be used for doubling and adding, without any exceptions or special cases. In contrast, consider the traditional chord-and-tangent group law on the Weierstrass model of an elliptic curve.  This group law can’t be applied to compute P + P, for example; instead, we have a separate doubling formula using the tangent. And until now, nobody has written down a single efficient complete addition law for the points on prime-order elliptic curves – including the prime-order curves that were standardized by NIST, and their international counterparts like Brainpool and ANSSI. This means that implementing standardized curves in a safe way is a much more complicated business than it should be!

Over twenty years ago, Bosma and Lenstra studied the group laws on elliptic curves. They concentrated on the case where an elliptic curve E is embedded in the projective plane as a Weierstrass model, but Arene, Kohel, and Ritzenthaler have since generalized their results to any projective embedding of any elliptic curve, and also to abelian varieties of any dimensions. To make things more precise, suppose E is an elliptic curve in projective Weierstrass form, with coordinates X, Y, and Z.  A group law is a triple of polynomials (F_X,F_Y,F_Z) such that P + Q = (F_X(P,Q):F_Y(P,Q):F_Z(P,Q)) for the pairs (P,Q) of points in some open subset of E\times E (the cartesian product of E with itself). This means that the group law is allowed to “fail” on some subset of the pairs of points on E, provided that subset is defined by a nontrivial algebraic relation. Basically, the group law is allowed to fail on what I will call a failure curve of points in the surface E\times E (this curve may be reducible; strictly speaking, it’s an effective divisor on E\times E). For any fixed P, there is a bounded number of Q such that the group law fails to add Q to P, and that bound depends only on the group law, not P.

To make this notion of failure more precise, we can add another requirement to the definition of a group law: for any pair (P,Q) of input points on E\times E, either (F_X(P,Q):F_Y(P,Q):F_Z(P,Q)) = P + Q (ie, the group law holds) or (F_X(P,Q),F_Y(P,Q),F_Z(P,Q)) = (0,0,0). From a computational point of view this is very nice, because (0,0,0) does not correspond to a projective point; so if we evaluate the group law at a pair of points then either the result is correct, or it is not a projective point – and this case is extremely easy to identify. If the formula is ever wrong, it’s so obviously wrong that you see it immediately.

A complete system of group laws is a collection of group laws that covers all of the pairs of points on E: that is, the common intersection of all of the failure curves is empty. Bosma and Lenstra showed that for an elliptic curve, any complete system must contain at least 2 group laws. However, this result only holds over the algebraic closure; and in cryptography, we don’t work over the algebraic closure, we work over a fixed finite field \mathbb{F}_q. And this is the crucial point: we can get away with just one group law, so long as none of the pairs of points on its failure curve are defined over \mathbb{F}_q! If they’re all defined over some extension, then they will never be inputs to our cryptographic algorithm, and we can simply ignore their existence.  Arene, Kohel, and Ritzenthaler take this to its logical conclusion, showing that this can always be done for any elliptic curve or abelian variety (apart from some pathological cases over extremely small fields, which are irrelevant to cryptography).

The particularly nice thing about Bosma and Lenstra’s paper is that they give a clear description of what the failure curves look like for the simplest nontrivial class of group laws, which is where all of the polynomials are biquadratic (that is, each F_X, F_Y, and F_Z is homogeneous of degree 2 in the coordinates of P, and also in the coordinates of Q). In this case, the failure curves all correspond to lines: for each group law (F_X,F_Y,F_Z), there is a line L in the projective plane such that the group law fails on (P,Q) if and only if P-Q is in the intersection of E with L.

At Eurocrypt, Joost Renes explained that there is an obvious way to apply this to prime-order elliptic curves: for a complete group law on such a curve E/\mathbb{F}_p, we can take the biquadratic group law whose failure line is the x-axis. This works because the intersection with E consists of the nonzero 2-torsion points – and since E(\mathbb{F}_p) has prime order, none of those are defined over \mathbb{F}_p, so they can’t be the difference of any pair of \mathbb{F}_p-points, and therefore the group law can’t fail on any pair of points in E(\mathbb{F}_p).  So far so good.  But Bosma and Lenstra actually wrote down that group law as an example in their paper, and the formulae take up a whole page and a half!  I’m sure that plenty of cryptographers had seen it, and thought “that’s all very nice in theory, but…”

So now we come to the main contribution of the paper: Joost, Craig, and Lejla show that this “it’ll never work” intuition is completely wrong.  They simplify the formulae (following Arene, Kohel, and Ritzenthaler); they derive efficient straight-line algorithms to evaluate the polynomials; and they show that not only can this group law be computed efficiently, it’s actually competitive with the best known (non-complete) formulae for projective Weierstrass curves.  So if you find yourself implementing the group law on a prime-order curve (for whatever reason, be it scientific or political), then you should definitely consider doing it the way their paper suggests.  You won’t lose much speed, and you’ll gain a lot of safety and simplicity.

–Ben Smith

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s