4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ @DannyNiu, that's not right. There are stronger attacks on the target group ($\mathbb{G}_T$) using the number field sieve, so you have to use a larger curve. The sizes of $\mathbb{G}_2$ and $\mathbb{G}_T$ can vary, but generally (iirc) $\mathbb{G}_2$ has a compact representation that takes only twice as many bits as an element in $\mathbb{G}_1$ and $\mathbb{G}_T$ will take 12 times as many bits as an element in $\mathbb{G}_1$. $\endgroup$ Jul 30 at 15:49
  • $\begingroup$ My knowledge with pairing is limited, and it's my pleasure to learn about it more. Do consider post a full answer. $\endgroup$
    – DannyNiu
    Jul 30 at 15:53
  • $\begingroup$ @AmanGrewal can you please post a full answer or provide the reference for the statement that G2 has a compact representation that takes only twice as many bits as an element in G1 and GT will take 12 times as many bits as an element in G1. It would be too kind of you, $\endgroup$
    – A B
    Jul 30 at 16:31
  • $\begingroup$ My knowledge is also limited, unfortunately. I would have to look up what appropriate sizes would be for 80-bit security. The 2x and 12x for $\mathbb{G}_2$ and $\mathbb{G}_T$ aren't hard fast rules. There exist other valid values, but these are common values that happen to do a good job balancing attacks in all three groups. I will find references and post them soon. $\endgroup$ Jul 30 at 22:15
5
+200
$\begingroup$

Element Size

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.

Key size and Signature size

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.

Public Key Choice

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.

Examples

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$.

$\endgroup$
5
  • $\begingroup$ This great answer would be even more useful if it explained what $r$ is; and what defines the size of the signature, public key, and (natural) private key in a reference application: BLS signature. $\endgroup$
    – fgrieu
    Aug 19 at 9:33
  • $\begingroup$ I can add signature sizes and the other stuff. What do you mean by $r$? $\endgroup$ Aug 19 at 15:07
  • 1
    $\begingroup$ I wish I knew! I'm refering to the thing with a size in bit on the right of that for $p$ in many tables of your reference. $\endgroup$
    – fgrieu
    Aug 19 at 15:12
  • 1
    $\begingroup$ I see. I'm pretty sure that's the order of the curve, but I'll double check. $\endgroup$ Aug 19 at 15:21
  • 1
    $\begingroup$ Added more information. I still want to double check what $D$ and $u$ are. And I want to add the cost/benefits of which group the public key is in. $\endgroup$ Aug 20 at 13:23

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.