BLS signature java implementation needed (if possible, along with some example code)

Question

I need to sign a string with the shortest digest possible using regular certificate like X.509. As far as I understand, I will have to transform the string to the sequence of bytes, then sign. After that I need to transform signature to the string also (so it can be passed from one human to another). I found out here that BLS algorithm is great for that and I want to try it out. Would you recommend some java implementation of it (would be great to have a code example along with that so I can avoid messing up with string to byte and vice versa transformings)?

Answer 1

The Boneh-Lynn-Shacham signature scheme works only in special elliptic curves that support efficient pairing computations. This is not something that you somehow add on top of an existing signature; it is a signature algorithm in its own right, that uses its own kind of public/private key pairs. If you want something that works with X.509, then you need a public key that can be encoded as part of an X.509 certificate. Currently, there is no defined format for a public key appropriate for BLS(*); X.509 is an open-ended standard so you could conceptually define your own format and make your own implementation, but:

1. This is an endeavour of considerable scope. It would require from you thorough knowledge of ASN.1 and DER encoding, elliptic curves, and pairings over elliptic curves (which is a plunge into rather hairy mathematics); and also strong skills at implementing cryptographic algorithms.

2. Since that would be your definition, there would be no interoperability with the implementation of anybody else, so your signatures would be verifiable only with your own software. At that point, why bother with X.509 at all ?

The advantage of BLS over a more common signature scheme, such as ECDSA, is that it produces shorter signatures. Shorter, not necessarily short. If you want n-bit security (traditionally, n = 128; current technological limit to the breakable is somewhere between 75 and 85), a BLS signature will need to have length at least 2n bits, while ECDSA requires 4n bits. Note that even with BLS, we are still talking about at least 200 bits or so, which is a lot for human-powered input. For instance, a Windows product key uses 25 characters taken in a 24-sign alphabet, which is sufficient to encode up to 114 bits, no more (because 24²⁵ is approximately equal to 2¹¹⁴). If you want human users to type signature values, then even with BLS you are considering an effort similar to entering two product keys (four product keys with ECDSA). In most contexts this is probably too much to ask (indeed, if you could ask for more, then Microsoft would also do it and use longer product keys, precisely so that they could use cryptographic signatures like BLS...).

If you still want to delve into BLS, then start with the PBC library. It is written in C, but the conversion C-to-Java is the least of your worries -- understanding the usage context and the maths is a lot harder. I am not aware of any openly available Java implementation of pairings, but it is absolutely doable (I can guarantee that, because at one point I wrote a pure Java implementation of pairings). Depending on your existing knowledge in maths, crypto and development, obtaining a functional, reasonably secure implementation could take you several years of full-time work. Personally, I have already done that once, so I know all the maths and crypto, and I have done a lot of crypto implementation in Java, and it would still take me at least two or three weeks of full-time work to produce something that could be described as "decent".

Edit: actually a simple Google search with terms "BLS signature java" uncovers jPBC, which appears to be a Java port of PBC. All my points about the need to understand the maths, and the interoperability issues, still hold.

---

^{(*) It is possible to encode a BLS public key using the generic format for elliptic curve public keys, but that format does not include any field to notify decoders that the curve is appropriate for any specific kind of pairing. Even if the software receiving that key can recompute the embedding degree, there is no way to indicate the pairing type to use (Weil, Tate, any distortion map...).}