Complexity of number field sieve theorem does not match with security of elliptic curves

Question

Number field sieve algorithm can is used to break discrete logarithm on field $F_{p^n}$. The algorithm has time complexity $\exp((c+o(1))\cdot(\log p^n)^{1/3}\cdot(\log \log p^n)^{2/3}$. Originally the constant $c$ is $(64/9)^{1/3} = 1.92$. Due to recent works, the more advanced Special extended tower number field sieve algorithm has $c = (32/9)^{1/3} = 1.54$.

Using this I tried to estimate the security of pairing-based elliptic curves. Consider BN256 curve. The pairing based elliptic curve has embedding degree 12. This means, the discrete log on BN256 can be mapped to discrete log on $F_{p^{12}}$, where $p$ is 256 bit prime. Now, on calculating the complexity of original NFS algorithm on $F_{p^{12}}$, we get roughly $$\exp(1.92 * (12*256)^{1/3} * (\log_2 (12*256))^{2/3}) = \exp(142.9) = 2^{206.16}$$ by wolframalpha (I ignored o(1) term for simplicity). So, BN256 curve originally provided 206 bit security. But in many places I saw that BN256 curve provided 128 bit security. Where I am doing wrong?

Edit: By @Poncho's answer, BN256 curve can be attacked better by pollard's rho algorithm. That justifies why BN256 is claimed to have 128 bit security earlier. After the recent Tower NFS algorithm, BN256 is claimed to have less than 110 bit security (Table in this blog). But when I calculate by wolframalpha, $$\exp(1.54 * (12*256)^{1/3} * (\log_2 (12*256))^{2/3}) = \exp(114.6) = 2^{165}$$. Therefore, even now, BN256 curve should have 128 bit security right?

Answer 1

If $L[\alpha, c] = e^{(c + o(1)) \cdot (\log p^n)^\alpha \cdot (\log \log p^n)^{1 - \alpha}}$ then $$\log_2 L[\alpha, c] = (c + o(1)) \cdot (\log p^n)^\alpha \cdot (\log \log p^n)^{1 - \alpha}/\log 2.$$

Let $p \approx 2^{256}$ and $n = 12$ so that $\log p^n \approx 12\cdot256\cdot \log 2 \approx 2130$; and let $\alpha = 1/3$, $c \approx 1.54$. Then, if we treat $o(1)$ as zero,

\begin{align} \log_2 L[\alpha, c] &\approx 1.54 \cdot (12\cdot256\cdot\log 2)^{1/3} \cdot [\log (12\cdot256\cdot\log 2)]^{2/3}/\log 2 \\ &\approx 111.15. \end{align}

You seem to have mixed up log bases in several places.

Answer 2

But in many places I saw that BN256 curve provided 128 bit security. Where I am doing wrong?

There are two potential attacks against the DLog problem in BN256

• The first is to attack the DLog problem in the finite field; that is, given the points $G$ and $H$, we compute $e(G, G)$ and $e(G, H)$, and then find the value $x$ with $e(G, G)^x = e(G, H)$.

• The other is to attack the DLog problem in the elliptic curve itself; that is, given the points $G$ and $H$, you use Pollards Rho (or Big-Step-Little-Step) to directly solve $xG = H$ (ignoring the pairing operation entirely).

As BN256 is a 256 bit curve, we know that the cost of the second approach is no more than an expected $2^{128}$ point additions, hence the security of the curve can be no more than 128 bits.