# Size of group elements in a bilinear context

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?

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.

• Thanks a lot. I have a last lexical question about "BLS and BN cases": is it type 3? Nov 3 at 9:42
• Yes, I believe that these are referred to as type 3. Nov 3 at 10:56