I was reading PBC and its implementations for finding pairing parameters. I am particularly interested in implementing a BLS signature scheme with 20-byte (160-bit) signatures ("short signatures"). So, I concluded that (for my app to have enough security) type G pairings are the best. However, it is really hard to find a type G pairing that produces signatures of 160-bit, but I noticed that "bits of q" in listfreeman.exe (to find appropriate discriminants that will then be passed to gengparam.exe) should be a number close to 160 for short signatures (with enough strength of course) to exist. So, I now run listfreeman.exe recording discriminant values with bits of q close to 160.

However, this process is taking forever and I was wondering whether I can find type G pairings producing 160-bit signatures with a faster way than by searching all discriminants?

  • 1
    $\begingroup$ Why using these curves? BN curves (type f in pbc) are more or less the "de facto standard" today. You could also look into more recent and optimized implementations such as available in relic. $\endgroup$ – DrLecter Aug 27 '14 at 6:27
  • $\begingroup$ @DrLecter First of all, type F pairings have dlog security 1920, while type G pairings have 10*n, which means that for n>192 type G has greater security. Second, I would prefer not to use relic, as "Disclaimer: RELIC is at most alpha-quality software. Implementations may not be correct or secure and may include patented algorithms. There are many configuration options which make the library horribly insecure. Use at your own risk." I don't like this disclaimer AT ALL and in PBC I can be sure that one of BLS inventors (Ben Lynn) maintains it... $\endgroup$ – Jason Aug 27 '14 at 9:35
  • $\begingroup$ Your fist statement is not true. Type G curves have an embedding degree of 10 and Type F curves (BN curves) an embedding degree of 12. So Type F curves are superior from that perspective. On a 160 bit curve this means Type G will give you 1600 bit dlog security and Type F curves will give you 1920 bit dlog security. $\endgroup$ – DrLecter Aug 27 '14 at 9:40
  • $\begingroup$ @DrLecter I don't know much about pairings, but is it true that the base field size is exactly the signature size? If yes, then I will definitely use Type F curves, but if not, I will have to restore the original question... $\endgroup$ – Jason Aug 27 '14 at 9:45
  • $\begingroup$ The signature in BLS signatures is one group element (curve point). So in affine coordinates you will have two times the size of the base field and if you use point compression you will get down to one element of the base field (+ the sign bit). So yes. Since the signature does not involve elements of the target group $G_T$ (which are larger in Type F than in Type G), Type F (BN curves) are the better choice. $\endgroup$ – DrLecter Aug 27 '14 at 9:49

Your Answer

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

Browse other questions tagged or ask your own question.