2
$\begingroup$

There are many pairing based elliptic curves like MNT curves, BN curves, SS curves etc., When we say BN256 curve, what does the number 256 indicate? Is it some group order or number of bits required to represent some group? How to figure out number of bits needed for representing each group G1, G2, and GT for curves like MNT224, BN256, SS512 etc.?

$\endgroup$
3
$\begingroup$

It's the size of the prime number of the underlying field in G1, G2 and GT.

In BN256, G1 is $E(\mathrm{GF}(p))$, G2 is a subgroup of $E(\mathrm{GF}(p^{12}))$ (or $E'(\mathrm{GF}(p^{2}))$ when using a twist) and GT is a subgroup of $\mathrm{GF}(p^{12})$.

Elements of G1 requires the same number of bits as $p$ for each elliptic curve point coordinate. Note that not all prime-friendly curves support cofactor 1, which means that in some cases we need a larger prime for a particular group order. (This is not the case in BN curves).

Elements of G2 require the same as $p^{k}$ for each elliptic curve point coordinate, where $k$ is the embedding degree of the curve. When using twists, we can reduce this by 2, 3, 4 ou 6 depending on the curve. BN curves have embedding degree 12 and support sextic twists, so we can use elements with the same size as $p^{12/6} = p^2$.

Elements of GT require the same size as $p^{k}$.

$\endgroup$
  • $\begingroup$ Since a point in elliptic curve has 2 coordinates, group element in G1 requires $2 * \log p$ bits to store. Am I right? Or is the $x$-coordinate enough to store a point? $\endgroup$ – satya May 24 at 16:38
  • $\begingroup$ Does the same explanation hold for MNT and SS curves? Embedding degree of MNT curves is 6. So in MNT curves, $G1$ is $E(GF(p))$, G2 is $E(GF(p^6))$ and GT is $GF(p^6)$. Are there any twists for MNT curves? $\endgroup$ – satya May 24 at 16:41
  • $\begingroup$ Does the number indicate anything about order of the groups? $\endgroup$ – satya May 24 at 16:42
  • $\begingroup$ @satya that's right. MNT has a quadratic twist; you can use $p^3$. The order of the curve is related to the field size via the Hasse theorem, in short they have basically the same size. However, we actually need a prime-order subgroup with big enough size. Some curves like BN support a prime-order subgroup size with the same size as $p$, some don't. Maybe that's material for another question... $\endgroup$ – Conrado May 24 at 16:50
  • $\begingroup$ What is embedding degree and twist for SS curves? For any elliptic curve, do we actually need 2 coordinates to store a point? Isn't one coordinate enough? $\endgroup$ – satya May 24 at 17:03

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.