6
$\begingroup$

I am using Ben Lynn's libpbc to implement a BLS threshold signature scheme and I am aiming for 128-bit security (i.e., a forgery attack should take around $2^{128}$ tries).

I was wondering what curves in libpbc would provide this level of security?

There are some indications about discrete log security here but I'm not sure how to interpret them. (I don't know too much about elliptic curve cryptography.)

For example, a "type A" curve with a "base field size" of 512 bits and embedding degree 2 is said to have 1024-bit discrete log security in the link above. Does that mean a successful attack on that curve takes around $2^{1024}$ operations? Or does it mean an attack on that curve is equivalent to an attack on a group $G(q) \subset \mathbb{Z}_p^*$ where $|q| = 1024$ bits?

Any tips would be appreciated!

Later edit: A more precise estimate of the security parameter of libpbc's curves would be nice!

$\endgroup$
4
$\begingroup$

The security of pairing-based cryptography relies on the security of the elliptic curve (which is linked to the size of underlying finite field, or "base field") and of the finite extension field being used.

The "Dlog security" column in the linked page is the size of the finite extension field. Its security used to be comparable to the corresponding RSA security; 1024 bits would provide only 80 bits of security. However, The "Dlog security" of the extension fields used in pairings has changed with some recent research, which makes things even more complicated. See Updating key size estimations for pairings, which estimates, for example, that a BN curve with a base field of 451 bits and "Dlog security" of 5532 bits would provide 128 bits of security)

The "Base field size" is related to the elliptic curve security; in this case security is usually half of the field size (to be precise: half the size of the prime-order subgroup). The "type A" curve there would provide 256 bits of security; but since the corresponding Dlog security is only 80 bits, the overall security is only 80.

Considering that, none of the listed benchmarked curves in the page you linked to provide 128-bit security. However, libpbc does support generating curves with arbitrary sizes for some pairing types, so it is possible to generate a pairing with 128-bit security.

$\endgroup$
  • $\begingroup$ Thank you! I guess it's time to read more about EC cryptography before I build something insecure. It looks like the MIRACL library offers 128-bit and up security for pairings (see bn_pair.cpp, kss_pair.cpp and bls_pair.cpp for 128, 192 and 256-bit security respectively) $\endgroup$ – Alin Tomescu Jun 28 '17 at 22:10
  • $\begingroup$ There is also RELIC (disclaimer: I used to contribute to it). In both cases just be aware that the provided parameters may not be up to date with these recent developments I linked to. $\endgroup$ – Conrado Jun 29 '17 at 2:53
  • $\begingroup$ Yes, I've heard about RELIC as well! I just benchmarked BLS signatures at the security levels above and computing the two pairings for verification is quite slow: 10ms on BN curve (128-bit), 100ms on KSS curve (192-bit) and 160ms on BLS curve (256-bit) (on an Intel i7-4870HQ CPU @ 2.50GHz). Will try RELIC next! $\endgroup$ – Alin Tomescu Jun 29 '17 at 17:16

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.