9
$\begingroup$

The Boneh–Lynn–Shacham signature is (as far as I know) unrivaled in compactness, promising $b$-bit security for $2b$-bit signature (perhaps: asymptotically).

Are there standard parameters for BLS signature, (being?) defined by standard bodies, security authorities, or other recognized authority; or otherwise common/recommended?

In particular, is there something with a size recommendation, perhaps in ISO/IEC 15946-5: Information technology - Security techniques - Cryptographic techniques based on elliptic curves - Part 5: Elliptic curve generation?

What does the state of the art ([BD 2019] I guess) implies about the size of BLS signature for $b$-bit security, for practical $b$ like 128?

Some references (now dated except the last two) :

[BLS 2004]: Dan Boneh, Ben Lynn, Hovav Shacham, Short Signatures from the Weil Pairing, in Journal of Cryptology, 2004 (originally [BLS2001] is proceedings of Asiacrypt 2001).

[BN 2005]: Paulo S. L. M. Barreto, Michael Naehrig, Pairing-Friendly Elliptic Curves of Prime Order, in proceedings of SAC 2005; slides.

[SSS 2006]: Mike Scott, Hovav Shacham, Terence Spies, P1363 presentation of 2006/10.

[NNS 2010]: Michael Naehrig, Ruben Niederhagen, Peter Schwabe, New software speed records for cryptographic pairings, in proceedings of Latincrypt 2010; software linked at referring page.

[ABLR 2013]: Diego F. Aranha, Paulo S. L. M. Barreto, Patrick Longa, Jefferson E. Ricardini, The Realm of the Pairings, in proceedings of SAC2013, with slides (reporting actual use since 2002).

[KB 2016]: Taechan Kim, Razvan Barbulescu, Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case, [KB16] in proceedings of Crypto 2016, originally [K 2015] of October 2015 and [B 2015] of November 2015.

[BD 2019]: Razvan Barbulescu, Sylvain Duquesne, Updating key size estimations for pairings, in Journal of Cryptology, October 2019

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ AFAIK a $b$-bit security for $2b$-bit signatures is no longer possible for 128-bit security or larger. The pairing-friendly family with prime-order group with the largest embedding degree were the BN curves, and they now require a larger base field to achieve the desired security. $\endgroup$
    – Conrado
    Commented Dec 4, 2019 at 17:38

2 Answers 2

Reset to default
6
+500
$\begingroup$

Well, the Boneh-Lynn-Shacham "BLS" signature scheme is currently in the process of being standardized through an Internet Draft named "draft-irtf-cfrg-bls-signature-00" (a working document of the Internet Engineering Task Force "IETF"), which you can track here. It appears Algorand might be behind this process, along with Dan Boneh's own support.

As stated in there:

There are two variants of the scheme:

  1. (minimizing signature size) Put signatures in G1 and public keys in G2, where G1/E1 has the more compact representation. For instance, when instantiated with the pairing-friendly curve BLS12-381, this yields signature size of 48 bytes, whereas the ECDSA signature over curve25519 has a signature size of 64 byes.

  2. (minimizing public key size) Put public keys in G1 and signatures in G2. This latter case comes up when we do signature aggregation, where most of the communication costs come from public keys. This is particularly relevant in applications such as blockchains and compressing certificate chains, where the goal is to minimize the total size of multiple public keys and aggregated signatures.

While they do not (yet) specify explicit parameters that are to be used, they do refer to the Internet Draft "Pairing Friendly Curves", which in turn has multiple recommendations depending on the level of security you want to reach. Regarding the above quote, it notably lists BLS12-381 in the recommendation to have 128 bits of security.

Also, when compared with ECDSA, they mention that (emphasize mine):

The following comparison assumes BLS signatures with curve BLS12-381, targeting 128 bits security.
[...]
In terms of sizes, ECDSA uses 32 bytes for public keys and 64 bytes for signatures; while BLS uses 96 bytes for public keys, and 48 bytes for signatures. Alternatively, BLS can also be instantiated with 48 bytes of public keys and 96 bytes of signatures. BLS also allows for signature compression. In other words, a single signature is sufficient to anthenticate multiple messages and public keys.

So it appears that the current "standard" is to have ~384 bits of signature to reach 128 bits of security, which means having $3b$ bits signatures for $b$ bits of security. (BN curves having "lost" favors, as Bristol said already and their current 128 bits contender being BN462.)

Also, notice this is a working document, and as such is not complete. For instance it is missing things that are yet to be added:

TBA: additional discussion on this, e.g. [Ristenpart-Yilek 06], and alternative mechanisms for securing aggregation against rogue key attacks, e.g. [Boneh-Drijvers-Neven 18]; there, pre-processing public keys would speed up verification.

And the rogue key attack is typically something important to defend against in the case where we want to have aggregate signatures, which is one of the nice features of BLS.

Notice that in pairing based crypto we had to move significantly our security estimates within the last 3 years most notably because of the advances in the FFDLP (see [KB16]), with your latest reference [BD 2019], being the current state of the art regarding security estimates and recommendations.

So it might still take a while until the above-mentioned IETF draft is finished and becomes an actual "standard", but this is in process.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ It's interesting to note that $3b$ signatures can be achieved without pairings by using truncated Schnorr signatures. $\endgroup$
    – Conrado
    Commented Dec 5, 2019 at 12:56
  • $\begingroup$ @Lery: I read in the abstract of this recent paper that the security of curves computed by Razvan Barbulescu, Nadia El Mrabet, Loubna Ghammam in 2019 should be revised, and "that at the 128-bit security level, BLS-12 and Fotiadis-Konstantinou-Martindale curves with k=12 over a 440 to 448-bit prime field seem to be the best choice for pairing efficiency" (I note the mention of efficiency rather size as the main goal). Does this, or any recent result, means that formerly proposed ≈384-bit BLS signature are not ≈128-bit secure? $\endgroup$
    – fgrieu ♦
    Commented Apr 14, 2020 at 14:14
  • $\begingroup$ @fgrieu Well, it would seem that not necessarily. For instance this is thankfully not the case if you were using BLS12-381 as discussed above, and it really depends on the curve you chose in the first place. They say in the paper: "For all curves but BN and BLS12, we obtain a lower estimated cost with optimised parameters". And actually Table 5 mentions an estimated security of 137 bits for BLS12-381. But good catch I must confess I hadn't seen that paper yet, thanks for sharing :) $\endgroup$
    – Lery
    Commented May 5, 2020 at 16:07
2
$\begingroup$

As a pairing-based scheme, my guess would be that IEEE 1363.3 is your best bet, but I don't have access to it from this computer.

The best implementation that I know of for these things is BN448 that was presented at RealWorldCrypto 2018. The constants in their constants.go must have come from somewhere - not necessarily a standards body, but Brendan is a well-known and competent cryptographer.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The author of BN448 apparently introduced it so that it "should be closer to the 128-bit security level". How far are we from $b$-bit security for $2b$-bit signature? $\endgroup$
    – fgrieu ♦
    Commented Apr 27, 2018 at 1:22
  • 1
    $\begingroup$ It seems that originally BN256 was intended to offer 128-bit security, realising the $2b$ signatures, but then new attacks were found. See the relevant link. Or see a thread view of the discussion. $\endgroup$
    – user2552
    Commented Apr 27, 2018 at 6:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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