Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I'm just studying the purpose of BN-Curves and I am interested in a setting for a 256-Bit security.
So could you tell or link me to any information about this?
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 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.
