3
$\begingroup$

I have read Pairings for cryptographers: It states that the groups $G_1$ and $G_2$ are groups of points on the curve and the group GT is a subgroup of the multiplicative group of a related finite field $F_{q^k}$. l is the order of these three groups. It then states that the sizes for $q$ are more comparable to RSA rather than like RCC. I implemented a type D curve. Lynn states for the type D curve that 170 bit for q (and l) should be sufficient.

I have problems to understand this all since I am missing some mathematical background. The size of q is very much depending on the type of curve. Or is Lynn's statement just outdated? When I implement a scheme based on this particular "type D"-curve, how do I define the security parameters and how do I justify my decision?

I would have thought, that the group operations in $G_1$ are the fastest and all others are slower, therefore this size matters. But now I think this is too easy and wrong.

$\endgroup$
4
$\begingroup$

Thats a bit outdated as for your choice of setting (with $k=6$) the 170 bit will give you 1020 bit security in the subgroup of $F_{q^6}^*$.

In your case for embedding degree 6 I would at least take 224 bits which would give you 1344 bits in the multiplicative subgroup of $F_{q^6}^*$ or you even go to 256 bits which will give you 1536 bits. Anyways the setting with embedding degree 6 will give you not an optimal efficiency-security tradeoff as you have to take far higher security levels in the curve to achieve acceptable security levels in $G_T$.

The choice of Baretto-Naehrig curves will give you the optimum security-efficiency tradeoff (they have $k=12$) today and they are for instance implemented in the RELIC toolkit.

You may look here what parameters for elliptic curves and multiplicative groups of finite fields are recommended today by different institutions.


Update (2021): As mentioned in the comments, already in 2014 the parameters mentioned above for MNT curves only gave security (far) below 100 bit. For an up to date reference on parameters one can look here: https://members.loria.fr/AGuillevic/pairing-friendly-curves/

$\endgroup$
4
  • $\begingroup$ Does this mean I should first take a look at multiplicative group requirements e.g. NIST until 2030: 2048 bit. Then I divide by k=12 which is about 170 bits for p? $\endgroup$ May 26 '14 at 14:45
  • $\begingroup$ @HorstLemke For 2048 bit NIST considers 224 bit for elliptic curves to be equivalent. So you have to find a tradeoff. If you go the other way round and take 224 bit for the curve and obtain 2688 bit for the multiplicative group you are on the safe side. $\endgroup$
    – DrLecter
    May 26 '14 at 14:57
  • $\begingroup$ Using a pairing with $G_T$ of only 1536 bits is bad advice (and already was bad advice in 2014, before the development of Kim–Barbulescu attacks). $\endgroup$ Mar 25 at 6:53
  • 1
    $\begingroup$ True, I think this gives a quite up to date overview: members.loria.fr/AGuillevic/pairing-friendly-curves $\endgroup$
    – DrLecter
    Mar 26 at 12:14
2
$\begingroup$

Lynn's advice was bad at the time, and is very outdated now. It was never secure to use 170-bit curves; for a start that would result in Pollard rho security of only 85 bits (assuming a prime-order curve). Worse, for an embedding degree of 6 you have a target extension field $G_T$ of only 1020 bits which is (as of 2021) probably breakable in practice.

The size of $G_T$ should not be less than 4500 bits, to resist Kim–Barbulescu attacks. Now I would recommend that you just use BLS12-381.

Note that keylength.com, referenced in DrLecter's answer, does not cover pairing-based cryptography.

$\endgroup$

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.