Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I am reading a paper based on elliptic curve bilinear pairing groups. The author has defined the size of private key, public key etc in terms of $|\mathbb{G}_1|, |\mathbb{G}_2|$ and $|\mathbb{G}_T|$.
For 80-bit security level, what are the sizes of $|\mathbb{G}_1|, |\mathbb{G}_2|$ and $|\mathbb{G}_T|$ in bits? I want to calculate the real size of the keys.
Thank you.
When choosing elliptic curve parameters, there is a lot of freedom. For the size of elements, the two parameters worth noting are the prime, $p$, and the embedding degree, $k$.
If $\mathbb{G}_1$ is an elliptic curve over $F_p$,1 then $\mathbb{G}_2$ is an elliptic curve over $F_{p^k}$, and $\mathbb{G}_T$ is a subgroup of $F_{p^k}$.
So elements of $\mathbb{G}_2$ and $\mathbb{G}_T$ require $k$ times the amount of storage as an element of $\mathbb{G}_1$.
However, all curves allow for compact representations of $\mathbb{G}_2$, using the twist of the curve, so that an element of $\mathbb{G}_2$ can be represented by a point on $E'\left(F_{p^\frac{k}{d}}\right)$, where $d$ is 2, 3, 4, or 6. All curves support $d=2$. Curves used for cryptographic operations will support larger $d$ because the cost of converting between representations is cheap.
BLS signatures are based on the pairing function $e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$.
Let $G_1$ be a generator for $\mathbb{G}_1$ and $G_2$ a generator for $\mathbb{G}_2$.
The private key, $x$, is just an integer between $0$ and $|\mathbb{G}_1|$, which is equal to $|\mathbb{G}_2|$. The public key, $X$, is either an element of $\mathbb{G}_1$ or $\mathbb{G}_2$. To sign a message, the message is hashed into an element of the other group, multiplied by the private key, and paired with the generator, i.e. $\sigma = e(G_1, xH(m))$. The signature, $\sigma$, is an element in $\mathbb{G}_T$. A verifier computes the pairing of the hash of the message with the public key as $e(X, H(m))$. If this equals $\sigma$, then the signature is valid.
Alternatively, the amount of data transmitted can be reduced and the amount of work the signer does can be reduced at the expense of the verifier doing more work. Instead of sending $\sigma$, the signer just sends $xH(m)$, and the verifier computes both pairings.
The public key can either be in $\mathbb{G}_1$ or $\mathbb{G}_2$. Elements in $\mathbb{G}_1$ are smaller. Operations in $\mathbb{G}_2$ are more expensive.
Take BLS12-3812, which is frequently cited to have 128-bit security. $p$ is 381 bits. The embedding degree, $k$, is 12, making $p^k$ have 4569 bits. An element in $\mathbb{G}_1$ takes 382 bits to represent (381 bits for 1 coordinate plus 1 bit for the sign). An element in $\mathbb{G}_2$ takes 762 bits to represent because there's a compact representation of it. An element in $\mathbb{G}_T$ takes 4596 bits to represent it.
From that same page2, MNT4-298 has about 77-bit security. For that curve, an element in $\mathbb{G}_1$ would require 299 bits; in $\mathbb{G}_T$, 1192 bits.
1 Technically, $\mathbb{G}_1$ is also defined over $F_{p^k}$, but since $E(F_p)$ is a subgroup of $E(F_{p^k})$, it doesn't quite matter.
2 These numbers come from https://members.loria.fr/AGuillevic/pairing-friendly-curves/. There's an explanation of some of the column names below.
Column Names
$k$ is the embedding degree.
$D$ is complex multiplication discriminant (I think).
$u$ is more complicated. I'm not entirely sure if this is correct. Each of these curve families (e.g., BLS or BN) relate $p$, $r$, and others to a "seed" parameter, $u$.
$p$ is the size of the characteristic of the field and the size of an element in $\mathbb{G}_1$.
$r$ is the size of the order of the curve.
$p^\frac{k}{d}$ is the size of the compact representation of an element in $\mathbb{G}_2$
$p^k$ is the size of an element in $\mathbb{G}_T$.
