# BN-Curves for 256-bit symmetric security

I'm just studying the purpose of BN-Curves and I am interested in a setting for a 256-Bit security.

• are BN-Curves efficient for this security issue?
• which embedding degree is recommended?
• what about ARM-Cortex M0-4 µC?

I'm searching for days now to get any information about this. But there is nothing that point out the usage of BN-Curves on that security-level.

• A quick look at this deck may be of use. – puzzlepalace Mar 15 '17 at 17:52
• I know this lecture. I read it once, but forgot it. Naehrig is only talking about the setup for 128-bit security. He lists, if r=512 then 256-bit security. But this draft [1] shows its less. Is it feasable to determine 256-bit sec with BN-Curves? [1] tools.ietf.org/id/… – Shalec Mar 15 '17 at 19:53

A BN-curve over a 256-bit prime field $\mathbb{F}_p$ has, being an elliptic curve, a 256-bit group attached to it, say of order $N$. As the best known attacks take $\approx\sqrt{N}$ times, this gives us 128-bits security against discrete logarithm attacks.

The curves also have embedding degree 12. That means we can use a pairing to map a discrete logarithm problem to $\mathbb{F}_{p^{12}}$. Given that $p\approx 2^{256}$, we know that $p^{12}\approx 2^{3072}$. Hence $\mathbb{F}_{p^{12}}$ is a 3072-bit finite field, and solving a DLP there should (see warning below) take about $2^{128}$ effort. So mapping the DLP to a finite field does not help an attacker, which is great.

If we move to 256-bit security, we will need a 512-bit group on the curve. Thus, we need to choose $p\approx 2^{512}$. The embedding degree remains 12, and we can still use the same pairing to map the DLP to $\mathbb{F}_{p^{12}}$. In this case $p^{12}\approx 2^{6144}$. According to the slides you refer to, this only gives a $<192$-bit security level. Thus $p\approx 2^{512}$ is too small for a 256-bit security level.

To obtain a 256-bit security level in the finite field, we actually need $p^{12}\approx 2^{15424}$ (according to the slides you refer to). Thus, $p\approx 1285$. This is very large, and will make computation very slow. Therefore BN-curves are great at 128-bit security level, as they make an optimal trade-off there, but do worse as the security level increases.

Warning: new attacks show that finite fields of size $2^{3072}$ do not actually provide a $128$-bit security level any more, although they did at the time of the proposal of BN-curves. So currently they are on shaky territory.

• Oh I see, thank you for your input. Is there any paper that specifies those thoughts on higher graded BN-Curves? Could you name one for me, please? It might be better to think about Goldilocks and four$\mathbb{Q}$ Curves. – Shalec Mar 17 '17 at 8:56
• If anywhere, probably the original paper (eprint.iacr.org/2005/133.pdf). I'm not sure if Goldilocks and Four$\mathbb{Q}$ are useful for the same applications as BN-curves.. – CurveEnthusiast Mar 17 '17 at 10:27
• @Shalec You might want to consider alternative curves (such as KSS or BLS) for higher security levels, as due to their embedding degree the security of the curve and the target group have a better matching. See for instance here: eprint.iacr.org/2012/232.pdf – DrLecter Mar 17 '17 at 14:37
• Ty for that input. I'm on my master thesis and I want to implement cryptographic pairings on an arm cortex m4 µ-controller at 256-bit of equivalent security. I just got told the Goldilocks and fourQ Curves. – Shalec Mar 17 '17 at 15:00
• @Shalec Have a look here ellipticnews.wordpress.com/2016/05/02/…, which contains some references. – CurveEnthusiast Mar 20 '17 at 7:39