2
$\begingroup$

I've previously asked questions on BN pairing parameters. Here's one more.

In the BN construction, one is working in a subgroup of a curve over an extension field $\mathbf{F}_{p^{12}}$ for some prime $p$. Now, in the scheme I'm looking at, they suggest selecting parameters so that $p$ will end up being a $256$-bit prime. Hence, the total field size will be around $2^{3072}$. The article claims this scheme has security equivalent to RSA 3072-bits.

Now, one can optimize the BN implementation by doing some of the calculations on the "sextic twist" since it turns out that there exists another curve over $\mathbf{F}_{p^2}$ which has a subgroup isomorphic to the subgroup of the original curve over the full field. I'm wondering, couldn't an attacker also use this to his advantage and to optimize his attack?

After all, the field now only has $p^2$ elements – so I'm wondering of the security really is still $p^{12}$ compared to RSA… or stated differently, why bother with such a high embedding degree when there's an isomorphic group over a much smaller field extension? Or is the attack that implies the equivalence to RSA 3072 bit not possible on the sextic twist, and that's why the full security is retained?

$\endgroup$
  • $\begingroup$ You speak of a subgroup of the curve over $F_{p^{12}}$. But you are working in a multiplicative subgroup of this field in the target group of the pairing. $\endgroup$ – DrLecter Feb 27 '14 at 8:05
1
$\begingroup$

A current conservative estimate of the security level of a BN curve with an extension field size of 3072 bits, taking into account the Kim-Barbulescu attacks, is 2110. See the paper http://eprint.iacr.org/2016/1102.pdf and the discussion of it at https://github.com/zcash/zcash/issues/714#issuecomment-263007229 . An earlier discussion of these attacks is https://ellipticnews.wordpress.com/2016/05/02/kim-barbulescu-variant-of-the-number-field-sieve-to-compute-discrete-logarithms-in-finite-fields/ .

$\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.