7
$\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?
Improve this question
$\endgroup$

1 Answer 1

Reset to default
12
$\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.
Improve this answer
$\endgroup$
6
  • 1
    $\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, 2018 at 20:48
  • 1
    $\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, 2018 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, 2018 at 17:01
  • 4
    $\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, 2018 at 6:55
  • 2
    $\begingroup$ @lovesh exactly. $\endgroup$
    – Youssef El Housni
    Dec 31, 2018 at 8:02

Your Answer

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

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