Security of EC pairings / BLS sigs

I copy a report I made about a year ago on the concrete security of BLS signatures.

Some recent work, like the following paper, is not included there:
https://hal.inria.fr/hal-02396352/document

The citations here are also relevant:
https://hackmd.io/@benjaminion/bls12-381#Security-level
(Generally, this is a pretty good primer on elliptic curve pairings)


Executive summary:

  1. The security of the BLS signature scheme is based on the hardness of the discrete logarithm problem (DLP) in a finite (extension) field GF(p^k), where k is relatively small.
  2. For this DLP there are pretty good algorithms to solve it.
  3. Popular curves are BN curves and BLS curves (BLS signature and BLS curves are two different things), where k=12.
  4. If we take p of ~256 bits, then p^k ~ 3072 bits. This is not believed to provide a 128-bit security.
  5. (It seems that) No one really knows what p should be in order to provide 128 bits of security. ~384 bits seems to be agreed upon; some (including Zcash) say it is conservative, however a recent work suggests p ~461 bits.
  6. It is an active research field, and DLP algorithms may improve.

Technical details:
First, BLS signatures is implemented using a bilinear pairing function from the group of points on an elliptic curve to a finite field GF(p^k), where k is called the embedding degree (k needs to be small in order to have an efficiently computable pairing).
Given a message m and a BLS signature [x]H, for H=H(m), we have that e([x]H,P) = e(H,P)^x = e(H,[x]P), where e is the pairing, P is a known point on the curve and [x]P is the public key.
Denote a = e(H,P), this is a point in GF(p^k), as well as a^x = e([x]H,P). If one can solve DLP in GF(p^k) then they could recover the secret key x and sign whatever they want.

A recent work from 2016 presented an improved attack against DLP in finite extension fields of small extension degree. The algorithm is called Extended Number Field Sieve.

While the asymptotic of this attack is understood, the attack running time on DLP with concrete parameters is at conflict:

  • Both [1] (see the table in the end) and [2, Table 9.4] estimate that log[p] =384 (k*log[p] = 4608) for 128-bit security for BN curves.
  • BLS curves are considered in [3, Table 4]. They give a similar approximation of log[p]=384 (k*log[p] = 4608) for 128-bit security.
  • The more recent survey [4] (one of its authors is one of the developers of the Extended Number Field Sieve) gives much higher values of log[p]=461 (k*log[p] = 5530) for 128-bit security for both BLS and BN curves. See Table 8, Table 11 (to get the value of log[p], BN should be multiplied by 4, BLS by 6) and Section 6.
  • These works are by very respectable cryptographers, and I won’t be surprised if they are very conservative in their estimations.
  • On the other hand, Zcash (see [5]) claims (see the footnote) that the analysis is conservative and missing some ingredients (at least for BN) and that BN curves over a 256-bit prime still provide 128 bit of security. Yet, it seems that they are not willing to take the risk, and instead of switching to BN384, they decided to work with BLS curves with log[p]=381 (k*log[p] = 4572).

Lastly, this area of research is still very active and it won’t be surprising at all if some breakthroughs would happen in the near future.

[1] https://ellipticnews.wordpress.com/2016/05/02/kim-barbulescu-variant-of-the-number-field-sieve-to-compute-discrete-logarithms-in-finite-fields/
[2] https://hal.inria.fr/hal-01420485v1/document
[3] https://eprint.iacr.org/2016/1102.pdf
[4] https://eprint.iacr.org/2017/334.pdf
[5] https://z.cash/blog/new-snark-curve/

1 Like

Hmmm … sounds kinda interesting and like the author knows what they’re talking about. I’m wondering why there isn’t there any response to the above post … :thinking: