5
$\begingroup$

I have some basic understanding of ECC - but pretty far from advanced concepts. I've been reading about BLS12-381 curve here and here, but I can't seem to fully understand it.

The things that I think I understand:

  • The order of the curve is $≈2^{381}$
  • The security level of the curve is 126 bits

The things that I don't understand:

  • What is the size of the private key for this curve? Assuming I'm right about the order, is it 381 bits?
  • The materials mention two generator points which produce public keys of different size - why is that? Shouldn't all points on the curve be of the same size?
  • What exactly is the subgroup $r$ and what is its significance?
$\endgroup$
7
$\begingroup$

The 12 in BLS12-381 means that the embedding degree is 12 and the 381 means that the prime in the finite field $\mathbb{F}_p$ is of 381 bits. Now talking about your bulletpoints:

  • The order is not $\approx 2^{381}$. The order is the number of points on the curve. A naive way is to find the coordinates $y$ in the equation $y^2=x^3+4$ for $x\in \{0, p-1\}$, or a better way you can run Schoof's algorithm.
  • The security level is around $128$ bits. In fact, you need a subgroup of order $r \approx 256$ bits to have this security level because Pollard's $\rho$ attack (the fastest known algorithm to find discrete logs on elliptic curves) has a complexity $\approx \mathcal{O}(\sqrt{r})$ and indeed for BLS12-381 $r \approx 2^{256}$.
  • The private key is a scalar in $\mathbb{F}_p$ which means $\in \{0, p-1\}$. So yes the size is $381$ bits.
  • The order of the curve is not prime. If it is prime all the generators will have the same order (and thus public keys of the same size) as all subgroups will have the same order as the curve. In fact, according to Lagrange theorem, the subgroups orders divide the group order so if it is a prime the subgroups orders will be equal to the group order. So, since in BLS12-381 it is not a prime, you have generators of different orders (which all divide the curve order). The reason behind this choice is that we can implement efficient pairings (https://eprint.iacr.org/2012/232.pdf).
  • see above.
$\endgroup$
  • $\begingroup$ Because BLS12-381 is used for pairings, it turns out the order needs to be larger than 256 bits to achieve 128 bit security. The elliptic curve discrete log problem is not the issue, it is the discrete log problem in the degree 12 extension of the field. Barbulescu and Duquesne ("Updating Key Size Estimations for Pairings", in Journal of Cryptology, Vol. 9, No. 1, 2018) suggest that you actually need around a 460 bit prime to obtain 128 bit security. $\endgroup$ – Bob Wall Nov 9 '18 at 19:31
  • $\begingroup$ Yes I agree, but it has to do with the discrete log. The pairing transforms the discrete log from the elliptic curve to GF(p^12). Up to Barbulescu paper, the discret log in finite fields was computed with GNFS which has a subexponential complexity and it turns out that the complexities ratio between pollard and GNFS is 12 but according to the paper the GNFS complexity can be further improved and that’s why you have to increase p size or the embedding degree k. Increasing p size in a BN curve results in subgroups of order as big as p whereas in BLS the sungroup order remains 256. $\endgroup$ – Youssef El Housni Nov 9 '18 at 20:48
  • $\begingroup$ @YoussefElHousni You mentioned that the curve order is not prime. But q and r in the implementation link posted by OP are both prime. $\endgroup$ – lovesh Dec 30 '18 at 15:30
  • 2
    $\begingroup$ @lovesh Let’s denote the curve order $n$. Neither $q$ nor $r$ are the curve order. $q$ is the base field modulus and the gap between $q$ and $n$ is at most $2\sqrt{q}$ (Hasse’s theorem). $r$ is the subgroup order which divides divides $n$ (Lagrange’s theorem). $\endgroup$ – Youssef El Housni Dec 30 '18 at 17:01
  • 1
    $\begingroup$ @YoussefElHousni Ok, so the total number of points on the curve are n but the number of points we work with is r so if if we are doing Diffie-Hellman we always check that the incoming point is in this subgroup of order r? $\endgroup$ – lovesh Dec 31 '18 at 6:55

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.