Score:2

Size of group elements in a bilinear context

cn flag

In a asymetric pairing context, which size (in bits) should have the elements of $\mathbb{G}_1,\mathbb{G}_2$ and $\mathbb{G}_T$ if we consider the most efficient elliptic curves?

Score:2
ru flag

In asymmetric, pairing-based cryptography $\mathbb G_1$ is usually a subgroup of an elliptic curve over a prime field $\mathbb F_q$. Elements of this group are usually expressed as a pair of numbers $(x,y)\in(\mathbb F_q)^2$. Computationally, both values are needed, but as $y$ can be recovered from $x$ up to sign elements are often compressed to an $x$ value and an additional bit for transmission purposes. This requires $\lceil\lg q\rceil+1$ bits.

$\mathbb G_2$ is usually a subgroup of the elliptic curve with the same equation but with points of $\mathbb F_{q^k}$ where $k$ is such that $\#\mathbb G_1|(q^k-1)$. Generically, such $k$ are hard to find, but there are various special constructions that parameterise suitable $q$ and curves for particular values of $k$. There is an especially nice family found by Barreto and Nehrig for $k=12$ which allows the whole elliptic curve group to be used for $\mathbb G_1$, which is particularly efficient. An earlier more general construction by Barreto, Lynn and Scott is almost as efficient with $k=12$ and $k=48$. In both the BN and BLS cases, elements of $\mathbb G_2$ can be expressed as a pair $(x,y)\in\mathbb (F_{q^k})^2$. Again compression is possible so that only $x$ and a sign bit need to be transmitted. This would require $k\lceil\lg q\rceil+1$ bits. In the BLS and BN cases, we can choose $\mathbb G_2$ in such a way that $x$ and $y$ and can be derived from a point on a related curve over $\mathbb F_{q^{k/6}}$. In such circumstances, it suffices to transmit a single element of $\mathbb F_{q^{k/6}}$ and a sign bit. This would require $\frac k6\lceil\lg q\rceil+1$ bits. However this choice of $\mathbb G_2$ is not compatible with all uses of pairing-based cryptography.

With such choices of $\mathbb G_1$ and $\mathbb G_2$ the various cryptographic pairing all map to $\mathbb G_T$ which is a multiplicative subgroup $\mathbb F_{q^k}$ of order $\#\mathbb G_1$. Elements of this group can be written as elements of $\mathbb F_{q^k}$ which takes $k\lceil\lg q\rceil$ bits.

The choice of $q$ and $k$ will depend on the level of security that you want your pairing-based system to have. The size of $\mathbb G_1$ needs to be large enough enought to block generic ``square root attacks'' and the size/structure of $\mathbb G_T$ needs to be sufficient to block the TNFS attack of Kim and Barbalescu. A 2019 draft from the IETF suggests the following in section 4.

Security (in bits) Size of $\mathbb G_1$ (uncomp./comp.) Size of $\mathbb G_2$ (uncomp./comp./BN-BLS comp.) Size of $\mathbb G_T$
100 512/257 6144/3073/513 (BN256, $k=12$) 3072
128 924/463 11088/5545/925 (BN462, $k=12$) 5544
128 922/462 11064/5533/923 (BLS12-461, $k=12$) 5532
128 762/382 9144/4573/763 (BLS12-381, $k=12$) 4572
256 1162/582 55776/27889/4649 (BLS48-581, $k=48$) 27888

Note that this is a purely classical security estimate and like all pairing systems these should be considered vulnerable to a cryptanalytically relevant quantum computer.

Ievgeni avatar
cn flag
Thanks a lot. I have a last lexical question about "BLS and BN cases": is it type 3?
Daniel S avatar
ru flag
Yes, I believe that these are referred to as type 3.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.