3

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.

Horst Lemke
  • 295
  • 1
  • 7

2 Answers2

4

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/

DrLecter
  • 12,547
  • 3
  • 43
  • 61
  • 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? – Horst Lemke May 26 '14 at 14:45
  • @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. – DrLecter May 26 '14 at 14:57
  • 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). – Daira-Emma Hopwood Mar 25 '21 at 06:53
  • 1
    True, I think this gives a quite up to date overview: https://members.loria.fr/AGuillevic/pairing-friendly-curves/ – DrLecter Mar 26 '21 at 12:14
2

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.

Daira-Emma Hopwood
  • 484
  • 3
  • 15