1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks a lot. I have a last lexical question about "BLS and BN cases": is it type 3? $\endgroup$
    – Ievgeni
    Nov 3 at 9:42
  • 1
    $\begingroup$ Yes, I believe that these are referred to as type 3. $\endgroup$
    – Daniel S
    Nov 3 at 10:56

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.