3
$\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$
1
  • $\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, 2014 at 8:05

1 Answer 1

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

On the specific question about the sextic twist, G_2 is still an elliptic curve group, not the multiplicative group of a finite field. So index calculus attacks, including variants of TNFS based on Kim and Barbulescu's work, do not apply to it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.