Are there any security risks in using Elliptic Curves defined over fields $\mathbf{F}_{p^n}$ where $n>1$

Question

I've recently been studying elliptic curves, and I've found that most of the current implementations use fields $\mathbf{Z_p}$ or in some cases $\mathbf{F}_{2^n}$. All the reasons I've seen for not using other extension fields are for reasons of efficiency.

I'm wondering if, efficiency aside, are there any security concerns inherent to using curves over $\mathbf{F}_{p^n}$ where $n>1$ and $p > 2$?

Answer 1

There are concerns on curves defined over an extension field. In particular for those of a small extension degree.

For a curve with a subgroup of prime order $r$, generally the best algorithm to solve the discrete logarithm problem has a complexity $O(r^{1/2})$. But there are attacks that use the structure of the extension field to get an algorithm with a smaller complexity.

• Weil descent. The finite field $\mathbf F_{q^n}$ can be viewed as a $\mathbf F_q$ vectorial space of dimension $n$: a polynomial equation defined over $\mathbf F_{q^n}$ can be viewed as $n$ polynomial equations defined over $\mathbf F_q$. It is possible to construct, under some conditions, a homomorphism from an elliptic curve $E$ defined over $\mathbf F_{q^n}$ to the jacobian a hyperellipti curve $H$ (the group associated to the curve, in the case of elliptic curve it is the curve itself) over the smaller field $\mathbf F_q$. $$ \varphi : E(\mathbf F_{q^n}) \to \mathrm{Jac}(H)(\mathbf F_q) $$ When this can be achieved, we can use better algorithms to solve the discrete logarithm on $\mathrm{Jac}(H)(\mathbf F_q)$. There are some limitations: for most curves $E$, the hyperelliptic curve produced has a high genus that makes algorithms much slower than on the elliptic curve.

• Algebraic approach. Index calculs method brought a better than square-root complexity for the discrete logarithm on the multiplicative group of a finite field. The idea is to decomposed random elements over a factor basis, and with enough relations and linear algebra, the discrete logarithme is solved. For elliptic curves over an extension field $\mathbf F_{q^n}$, the factor basis can be defined as: $$ \mathcal F = \{ P \in E(\mathbf F_{q^n}) \mid x(P)\in \mathbf F_q\}. $$ Suppose $n=2$ and you want to decompose a point $R=(x_R, y_R)$ into two points of $\mathcal F$. There exist a polynomial $S_3$ such that if $S_3(x_1, x_2, x_3) = 0$, then there exists $P_1, P_2, P_3$ with $P_1 + P_2 + P_3 = \infty$. It can be used to solve the system $$ \begin{array}{l} S_3(x_1,x_2,x_R) = 0 \\ x_1, x_2 \in \mathcal F \end{array} $$ And $S_3$ can be viewed as $2$ polynomial equations over $\mathbf F_q$ and since $x_1$ and $x_2$ are already in the subfield, we have a polynomial system (non-linear, unfortunately) of $2$ equations and $2$ variables that can be solved by computing a Groebner basis. This can be generalized for bigger $n$. This approach has lead to an algorithm of heuristic complexity $\tilde{O}(q^{2-2/n})$ which is faster than the square-root algorithm when $n\geq 3$. One drawback is that there is a constant $n!$ on the complexity.

You can find a survey from 2015, Recent progress on the elliptic curve discrete logarithmproblem that talks about the above and more. Attemps have been made to apply the algebraic approach for curves over a prime field $\mathbf F_p$ but have failed (a factor basis that can be translated algebraically is harder to find without having a polynomial of high degree, which makes is very difficult to solve non-linear polynomial system).

To prevent the above attacks, it is recommanded to have a finite field of prime degree which is the case for most of binary standardized curves ($\mathbf F_{2^n}$ with $n$ prime), but not all, or use a curve defined over a prime field.