BLS Curves

Over twenty years ago, I was focused on BLS short signatures. Our paper spoke of fields of characteristic 3, which turns out to be a fatal weakness. Coppersmith showed discrete log problems over low-characteristic fields were susceptible to special attacks that reduced their security.

Dan Boneh directed me to a paper by Miyaji, Nakabayashi, and Takano that described how to find elliptic curves with the property we needed for our signature scheme, namely, we get all the desired torsion points in a field extension of low degree so we can compute pairings. This degree is sometimes called the embedding degree or security multiplier.

I was ignorant of the inner workings of their algorithm (it uses the Complex Multiplication method, whose details I still have yet to study!), but dutifully followed the steps, which involves finding a prime with a certain polynomial to produce a curve with embedding degree 6.

We were saved! We could abandon the curves in our paper, and switch to pairing-friendly curves over high-characteristic fields.

Or were we? We had boasted of secure 160-bit signatures. With an embedding degree of 6, it meant an adversary had a choice between a generic attack against an 160-bit elliptic curve, or a specialized attack like index calculus in a 960-bit finite field. In those days, the gold standard for the latter was 1024 bits. (960 is close enough!)

Although switching curves warded off Coppersmith attacks, researchers kept improving attacks on finite fields of any characteristic. Soon, 2048 was the new 1024, boding ill for our short signature scheme. It now seemed we needed an embedding degree of 12, so we could get 160-bit signatures while forcing an adversary to face a 1920-bit field when using finite-field attacks.

We only knew about low-degree curves with at most embedding degree 6. How do we go beyond?

Lacking a deep understanding, my first thought was naive and obvious. Why not try a different polynomial in the MNT method? Perhaps I’d magically get a higher degree. Out of laziness, I wrote code to explore for me. It generated random polynomials and checked if they led to the curves I sought.

My program found something! It reported that a certain polynomial led to an embedding degree of 8. But elation turned into dismay when I realized that unless I solved a nasty quartic Diophantine equation, I could only construct toy examples. I dismissed my finding as a curiosity with little value.

Luckily, around April 2002, Paulo started an email thread with Mike and I on an idea for constructing embedding degree 10 curves. He added that degree 8 seemed elusive. I was unable to build on his idea, but it seemed appropriate to mention what my program had found:

I could hardly keep up with the ensuing discussion. I was flabbergasted when Paulo and Mike soon figured out how to construct a curve with any given embedding degree. The method was ingenious, yet simple, using nothing more than cyclotomic polynomials. I felt silly for writing so much code to slowly rediscover a special case of something so well-known.

Paulo and Mike sent me a draft of a paper they had written, and graciously invited me to join. I had nothing to add. Finding the initial example was my only contribution. I merely made changes like reordering the sections to make their discoveries easier to understand for me.

Despite the breakthrough, I was disappointed due to a snag in the algorithm. While it could produce cryptographically useful curves, they were not short-signature-ly useful curves. The "cofactors" were huge: obtaining 160-bit security against generic discrete log attacks might need a 320-bit finite field and hence imply a 320-bit signature, which is no better than standard non-pairing-based elliptic curve signatures. Ultimately, the paper led me no closer to my goals.

Indeed, I thought the paper was doomed to obscurity, especially when researchers (including Paulo and Mike) found the holy grails that I never did: they built curves with higher embedding degrees like 10 and 12 with trivial cofactors. Thus there ought to be even fewer reasons to fiddle with cyclotomic polynomials. Meanwhile, I graduated, and left academia for industry.

A decade later, I was shocked on discovering that Paulo and Mike’s words written in 2002 proved to be prescient. Because of advances in research, the method outlined in our paper turns out to produce good curves for pairing-based cryptosystems. For now, "BLS curves" are a thing, and funnily enough, they are used for BLS signatures. The cofactor is irrelevant because the signature length is not always important: BLS signatures have several other useful properties.

My first step was fine. When faced with a mysterious problem, guessing wildly can throw off a few sparks that light the way to deeper understanding. However, guessing alone is almost never enough. I only got away with it because of chance correspondence with a couple of generous geniuses.

I probably should have learned to use a popular computer algebra system, or at least used a language with a REPL. Instead, my experiments marched to the rhythm of the edit-compile-run cycle of C++. Then again, at the time, I had just implemented some pairing-based cryptosystems using the NTL library, so I was accustomed to the slow pace.

The following is a later version of my disturbingly simple program whose output was responsible for getting my name on a paper. The first version was non-deterministic, but higher coefficients never seemed to show up. I guessed that although polynomials with higher coefficients might work, the program would have to win a lottery to hit upon the right numbers so I reduced the scope of the search, making an exhaustive approach practical.

The following might be its output. I’m unsure, because I have long forgotten the matching between output files and source files, and I’m too lazy to reconstruct the environment in which my program ran.