1

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)?

3

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 2425 is approximately equal to 2114). 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...).

  • Thank you very much for your effort, Thomas, it is really useful and interesting. How can we estimate the trade-off between usability and security in case of shortening the key? (I don't really understand why current technological limit is defined by you as nearly constant value — isn't it just a matter of time and computational resources when any protection mechanism will be broken?) Please tell me if it's already point I should start asking new question rather then discussing at comments. – Poliakoff Jan 29 '16 at 14:38
  • Computational resources that can be mustered by any attacker are limited by his budget, to buy hardware and to buy electricity to power the said hardware. There is only so much you can have with a billion dollars. Technological advances tend to increase the amount of computing you can do with a given budget; look up "Moore's law". Right now, a rich organization (say, Apple or Google) may have the cash necessary to envision a 2^80 or so breaking effort, though of course they will do it only if the result is worth it. – Thomas Pornin Jan 29 '16 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.