A jq255 Elliptic Curve Specification, and a Retrospective

First things first: there is now a specification for the jq255e and jq255s elliptic curves; it is published on the C2SP initiative and is formally in (draft) version 0.0.1: https://github.com/C2SP/C2SP/blob/main/jq255.md

The jq255e and jq255s groups are prime-order groups appropriate for building cryptographic protocols, and based on elliptic curves. These curves are from the large class of double-odd curves and their specific representation and formulas are described in particular in a paper I wrote this summer: https://eprint.iacr.org/2022/1052. In a nutshell, their advantages, compared to other curves of similar security levels, are the following:

• They have prime order; there is no cofactor to deal with, unlike plain twisted Edwards curves such as Curve25519. They offer the same convenience for protocol building as other prime order groups such as ristretto255.
• Performance is good; cost of operations on curve points is similar to that of twisted Edwards curves, or even somewhat faster. This is true on both large systems (servers, laptops, smartphones) and small and constrained hardware (microcontrollers). On top of that, jq255e (specifically) gets a performance boost for some operations (multiplication of a point by a full-width scalar) thanks to its internal endomorphism.
• Signatures are short; digital signatures have size only 48 bytes instead of the usual 64 bytes of Ed25519 signatures, or ECDSA over P-256 or secp256k1. This is not a new method, but only the application of a technique that has been known since the late 1980s, but was overlooked for some unclear reasons. The reduction in size also makes verification faster, which is a nice side effect.
• Implementation is simple; the formulas are straightforward and complete, and the point decompression only requires a square root computation in a finite field, without needing the combined square-root-and-inversion used in ristretto255.

The point of having a specification (as opposed to a research paper) is to provide a practical and unambiguous reference that carefully delineates potential pitfalls, and properly defines the exact encoding rules so that interoperability is achieved. Famously, Curve25519 was not specified in that way, and implementations tried to copy each other, though with some subtle differences that still plague the whole ecosystem. By writing a specification that defines and enforces canonical encodings everywhere, along with a reference implementation (in Python), I am trying to avoid that kind of suboptimal outcome. In jq255 curves, any public key, private key or signature value has a single valid representation as a fixed-size sequence of bytes, and all decoding operations duly reject any input that does not follow such a representation.

The specification is currently a “draft” (i.e. its version starts with “0”). It is meant to gather comments. As per the concept of C2SP, the specification is published as a GitHub repository, so that comments and modifications can be proposed by anybody, using the tools of software development (issues, pull requests, versioning…). It is my hope that these curves gain some traction and help avoid some problems that I still encounter regularly in practical uses of elliptic curve cryptography (in particular related to the non-trivial cofactor of twisted Edwards curves).

This specification is the occasion, for me, to look back at the research I made in the area of elliptic curve cryptography over the past few years. The output of that research can be summarized by the list of corresponding papers, all of which having been pushed to the Cryptology ePrint Archive:

• https://eprint.iacr.org/2020/009: Efficient Elliptic Curve Operations On Microcontrollers With Finite Field Extensions
• https://eprint.iacr.org/2020/454: Optimized Lattice Basis Reduction In Dimension 2, and Fast Schnorr and EdDSA Signature Verification
• https://eprint.iacr.org/2020/1558: Double-Odd Elliptic Curves
• https://eprint.iacr.org/2022/274: EcGFp5: a Specialized Elliptic Curve
• https://eprint.iacr.org/2022/938: Truncated EdDSA/ECDSA Signatures
• https://eprint.iacr.org/2022/1052: Double-Odd Jacobi Quartic
• https://eprint.iacr.org/2022/1164: Point-Halving and Subgroup Membership in Twisted Edwards Curves
• https://eprint.iacr.org/2022/1325: Efficient and Complete Formulas for Binary Curves

The following trends can be detected:

• All these papers are about elliptic curves as “generic groups” for which the discrete logarithm problem is believed hard. I did not pursue research (or, more accurately, I found nothing worth publishing) in the area of pairing-friendly elliptic curves, which are special curves with extra properties that enable very nifty functionalities (notably BLS signatures).
• I always try to achieve a practical benefit in applications, such as making things run faster, or use shorter encodings, with some emphasis on small software embedded systems (i.e. microcontrollers using a small 32-bit CPU such as the ARM Cortex M0+). Small embedded systems tend to be a lot more constrained in resources, and sensitive to optimizations in size and speed, than large servers where CPU power is plentiful and the cost of cryptography in an application is mostly negligible. All papers include links to corresponding open-source implementations that illustrate the application of the described techniques.
• Whenever possible, I try to explore interoperable solutions; the inertia of already deployed systems is a tremendous force that cannot be dismissed offhandedly, and it is worth investigating ways to apply possible optimizations in the implementation of existing protocols such as EdDSA or ECDSA signatures, even if better solutions could be designed (such as jq255 curves and their signatures).

The first paper in the list above defines a prime-order elliptic curve called Curve9767. The main idea is to use a field extension. Elliptic curves are defined over a (finite) field, where all computations are performed. Usually, we work over the field of integers modulo a given big prime, and we choose the prime such that computations in that field are efficient (for instance, Curve25519 uses the prime 2²⁵⁵-19). In all generality, finite fields have order p^m for some prime p (the “field characteristic”) and integer m ≥ 1 (the “extension degree”); for a given total field size (at least 2²⁵⁰ or so, if we want to claim “128-bit security”), the two ends of the spectrum are m = 1 (the field has order p, this is the case of Curve25519 or P-256) and p = 2 (the field has order 2^m, as is used in some standard NIST curves such as K-233; more on that later on). Situations “in between”, with a small-ish p but still quite greater than 2, are not well explored, and have some potential security issues that must be carefully avoided (e.g. degree m should not admit a too small prime divisor). Curve9767 uses a field which is, precisely, such an intermediate case, with p = 9767 and m = 19. This field happens to be a sweet optimization spot on, specifically, the ARM Cortex M0+ CPU, yielding good performance, in particular for computing divisions in the field. However, implementations on other architectures (including a slightly larger ARM Cortex M4 microcontroller) yielded only disappointing performance. The experience gathered in that research was not lost; I could reuse it for ecGFp5, whose field uses p = 2⁶⁴-2³²+1 and m = 5; this is a specialized curve meant for virtual machines with zero-knowledge proofs (e.g. the Miden VM).

Double-odd elliptic curves are a category of curves that had been somewhat neglected previously. Most “classic” research on elliptic curves focused on curves with a prime order, since a prime-order group is what is needed to build cryptographic functionalities such as key exchange (with Diffie-Hellman). When a curve order is equal to rh, for some prime r and an integer h > 1 (h is then called the “cofactor”), protocols built on the curve must take some extra care to avoid issues with the cofactor. Not all protocols were careful enough in practice. Montgomery curves, later reinterpreted as twisted Edwards curves, have a non-trivial cofactor (h is always a multiple of 4 for such curves). Sometimes, the cofactor’s deleterious effects can be absorbed at relatively low cost at the protocol level, but this always requires some extra analysis. Twisted Edwards curves, in particular, offer very good performance with simple and complete formulas (no special case to handle, and this is a very good thing, especially for avoiding side-channel attacks on implementations), but their simplicity is obtained at the cost of pushing some complexity into the protocol. Twisted Edwards curves with cofactor h = 4 or 8 can be turned into convenient prime-order groups, thereby voiding the cofactor issues, through the Decaf/Ristretto construction; this is how the ristretto255 group is defined, over the twisted Edwards Curve25519. With double-odd curves, I explored an “intermediate” case of curves with cofactor h = 2, over which a prime-order group can be built with similar techniques. I recently reinterpreted such curves as a sub-case of an equation type known as the Jacobi quartic, and that finally yielded a prime-order group with all the security and convenience that can be achieved with ristretto255, albeit with somewhat simpler formulas (especially for decoding and encoding points) and slightly better performance. That result was worth describing as a practical specification so that it may be deployed in applications, hence the jq255 document and reference implementation with which I started this present blog post.

Another way to handle cofactor issues is through a validation step, to detect and reject points which are not in the proper prime-order subgroup. This can be done at the cost of a multiplication by the subgroup order (denoted r above), which is simple enough to implement, but expensive. In the case of curves with cofactor 4 or 8, a faster technique is possible, which halves that cost. This paper was meant mostly in the context of FROST signatures, where such validation is made mandatory (for the Ed25519 cipher suite). Even so, this is still expensive, and real prime-order groups such as ristretto255 (or, of course, the jq255 curves) are preferable.

Some of my elliptic curve research was yet one level higher, i.e. in the protocols, and specifically in the handling of signatures. The core principle of signatures on prime order groups was described by Schnorr in the late 1980s; for unfortunate patent-related reasons, a rather clunky derived construction known as DSA was standardized by NIST, and adapted to elliptic curves under the name ECDSA. In 2012, EdDSA signatures were defined, using the original Schnorr scheme, applied to twisted Edwards curves; when the curve is Curve25519 (a reinterpretation, with a change of variables, of a Montgomery curve defined in 2006), the result is called Ed25519. The verification of an ECDSA or EdDSA signature is relatively expensive; an optimization technique for this step, by Antipa et al, was known since 2005, but it relied on a preparatory step which was complicated to implement and whose cost tended to cancel the gains from the optimization technique. That preparatory step could be described as a case of lattice basis reduction in dimension two, with an algorithm from Lagrange, dating back to the 18th century (the roots of cryptographic science are deep). In 2020, I described a much faster, binary version of Lagrange’s algorithm, allowing non-negligible gains in the performance of signature verification, even for fast curves such as Curve25519.

ECDSA signatures, on a standard curve with 128-bit security (e.g. NIST’s P-256, or the secp256k1 curve used in many blockchain systems), have size 64 bytes (in practice, many ECDSA signatures use an inefficient ASN.1-based encoding which makes them needlessly larger than that). Ed25519 signatures also have size 64 bytes. The signature size can be a problem, especially for protocols dealing with small embedded systems, with strict constraints on communication bandwidth. A few bits can be removed from a signature by having the verifier “guess” their value (through exhaustive search), though this increases the verification cost; this can be done for any signature scheme, but in the case of ECDSA and EdDSA, leveraging the mathematical structure of the signatures allows somewhat larger gains, to the extent that it can be practical to reduce EdDSA signatures down to 60 bytes or so. This is a very slight gain, but in some situations it can be a lifesaver. Importantly, this technique, just like the speed optimization described previously, works on plain standard signatures and does not require modifying the signature generator in any way; these are examples of “interoperable solutions”.

Last but not least, I could apply some of the ideas of double-odd curves to the case of binary curves. These are curves defined over finite fields of cardinal 2^m for some integer m. To put it in simple words, these fields are weird. Addition in these fields is XOR, so that addition and subtraction are the same thing. In such a field, 1 + 1 = 0 (because 2 = 0). Squaring and square roots are linear operations; every value is a square and has a single square root. Nothing works as it does in other fields; elliptic curves must use their own specific equation format and formulas. Nevertheless, standard curves were, quite early, defined on binary fields, mostly because they are amenable to very fast hardware implementations. Among the fifteen standard NIST curves, ten are binary curves (the B-* and K-* curves, whereas the five P-* curves use integers modulo a big prime p). In more modern times, binary curves are mostly neglected, for a variety of non-completely scientific reasons, one of them being that multiplications in binary fields are quite expensive on small microcontrollers; however, such curves may be very fast on recent CPUs, and are certainly unbroken so far. Using techniques inspired by my previous work on double-odd curves (and many hours of frantic covering of hundreds of sheets of paper with scrawled calculations), I could find formulas for computing over such curves with two advantages over the previously known best formulas: they are complete (no special case for the neutral point, or for adding a point to itself), and they are faster (generic point addition in 8 field multiplications instead of 11). Applying these formulas to the standard curve K-233, I could get computations of point multiplications by a scalar under 30k cycles on a recent x86 CPU, more than twice faster than even the endomorphism-powered jq255e.

A synthetic conclusion of all this is that the question of what is the “best” curve for cryptography is certainly not resolved yet. I could produce a number of optimizations in various places, and my best attempt at general-purpose, fast-everywhere curves are jq255e and jq255s, which is why I am now specifying them so that they may be applied in practical deployments in an orderly way. But some improvements are most probably still lurking somewhere within the equations, and I encourage researchers to have another look at that space.