Original BLS Signature Code

Short Signatures from the Weil Pairing appeared at the ASIACRYPT2001 conference. For memory, Dan Boneh came up with the idea and Hovav Shacham did the proofs. I got the easy job: they put my name on the paper for implementing the scheme to get some benchmarks. We didn’t need impressive numbers; we merely hoped to allay fears that it was too slow to be practical.

I had meant to release the code shortly after our paper was published, but it didn’t happen. Perhaps I felt it was less urgent because I soon released code that was better at computing pairings. Or perhaps it was because we later learned that fields of characteristic 3 were best avoided.

Nonetheless, I never quite forgot this tiny piece of unfinished business. I almost don’t care. But only almost.

Therefore, close to 20 years later, I’m at last releasing the code from the paper. I’m at peace with the realization that I’ll most likely never clean up the code, so I’m posting the files as they were after I last touched them so long ago:

I included the object files and binaries because I worry I’d mess up even a light dusting.

I called it SSS for Stanford short signatures. Naturally, I’m delighted nobody else called it that, and instead they’re now called BLS signatures!

I wrote the code before I used version control. More accurately, my version control was to make tarballs now and then, and record changes in a text file, which in this case is called HISTORY.

I used Victor Shoup’s NTL library to offload various constructions from number theory, and also because Victor happened to be visiting Stanford at the time.

Since my first project at Stanford was to implement the Boneh-Franklin Identity-Based Encryption scheme, I had short signatures working in no time. Pleased I had completed my assigned task so quickly, I proudly announced the results to Dan. I was crestfallen when he replied that several minutes for signature verification was far too slow.

Luckily, Victor gave me plenty of good advice which helped me optimize the code enough to obtain acceptable benchmarks.

I developed on my office computer, which was a Pentium III 1GHz running Debian, likely the "testing" distribution.