Why are elliptic curves over binary fields used less than those over prime fields？

Question

In practical applications, elliptic curves over $F_p$ seem to be more popular than those over $F_{2^n}$. Is it because operations over prime fields are faster than those over $F_{2^n}$ for the same security level?

Maybe it is my imagination. I just see many more open projects using elliptic curves over $F_p$ but not as many over $F_{2^n}$.

Answer 1

Security: Binary fields has more attack vectors than prime fields

The Discrete log on ECCs with the binary field is not broken. That is not the reason. Bernstein said;

the security story for non-prime fields (e.g., binary extension fields) is more complicated and less stable than the security story for prime fields, as illustrated by 1998 Frey, 2002 Gaudry–Hess–Smart, 2009 Gaudry, and 2012 Petit–Quisquater.

As a result, choosing prime fields reduces the attack vectors, so there are fewer concerns for security.

• 2002 Constructive and Destructive Facets of Weil Descent on Elliptic Curves

  In this paper we look in detail at the curves which arise in the method of Galbraith and Smart for producing curves in the Weil restriction of an elliptic curve over a finite field of characteristic two of composite degree. We explain how this method can be used to construct hyperelliptic cryptosystems which could be as secure as cryptosystems based on the original elliptic curve. On the other hand, we show that this may provide a way of attacking the original elliptic curve cryptosystem using recent advances in the study of the discrete logarithm problem on hyperelliptic curves

• 2004 Index calculus for abelian varieties and the elliptic curve discrete logarithm problem by Pierrick Gaudry

  We have shown that asymptotically, elliptic curves defined over small-degree extension fields are weaker than those defined over prime fields or large prime-degree extension fields.

• 2012 On Polynomial Systems Arising from a Weil Descent by Christophe Petit and Jean-Jacques Quisquater

  They have looked at ECDLP on the binary extension field and show that their algorithm outperforms the generic discrete logarithm algorithms for $N >2000$. The recommended sizes are not affected, yet!

---

Patents of the Certicom ( and others)

Another important issue is the patents that mainly the Certicom has/had.

First Bruce Schneier's quote

"Certicom certainly can claim ownership of ECC," Schneier told us. "The algorithm was developed and patented by the company's founders, and the patents are well written and strong. I don't like it, but they can claim ownership."

• One of the patents of the Certicom was about efficient $\operatorname{GF}(2^n)$ multiplication in normal basis representation; U.S. Patent 5,787,028. This patent granted in 1998 and finally expired in 2016.
• NSA had some patents on $\operatorname{GF}(2^n)$, too; [1] [2] [3] [4], however, they are expired much earlier since NSA did not paid the fees ( I think that was deliberate)

---

Current stage of the attacks to compare

If we look at the Certicom's ECC challenges

• A Koblitz curve over $2^{108}$ is broken in 2000.
• A $109$ bit prime curve is broken in 2002.
• A curve over $2^{109}$ is broken in 2004.
• 131-bit Binary or Prime challenges are not broken, yet.

Apart from these challenges;

• 117.35-bit elliptic curve discrete logarithm problem on a binary curve is broken in 2016 by Bernstein et. al

Answer 2

A down-to-earth fact shifting the balance towards $\mathbb F_p$ is that standard CPUs of the 1990s and early 2000s often had multiply instructions but no hardware support for carry-less product, reversing the advantage $\mathbb F_{2^k}$ has in hardware. And arithmetic in $\mathbb F_p$ had been extensively studied for RSA and DSA. So it's understandable people started using $\mathbb F_p$, and then there was no compelling reason to change. Perhaps (per in this comment) Certicom's patents on ECC in $\mathbb F_{2^k}$ drove propects away. Also, more people understand arithmetic in $\mathbb F_p$, and nobody ever got fired for choosing it.

From a security standpoint, I think there is a reasonable feeling that with $\log_2p\approx m$, ECC in prime field $\mathbb F_p$ is safer than in binary field $\mathbb F_{2^m}$. The reasons I understand are:

• For a given $m$, there are about $\approx0.69\cdot2^m/m$ choices for $p$. All finite fields of a given order are isomorphic. So $\mathbb F_{2^m}$ is a special case, and in crypto, special cases seldom are safer.
• In hardware at least, ECC point addition is significantly more costly in field $\mathbb F_p$ than in field $\mathbb F_{2^m}$. Perhaps harder imply safer, and harder implying less safe would be quite surprising.
• Solving the DLP in the multiplicative subgroup of field $\mathbb F_p$ is much harder than for $\mathbb F_{2^m}$, as can be seen from the records ($795\text{-bit }p$ in $\mathbb F_p$, $m=30750$ in $\mathbb F_{2^m}$ ). Again, perhaps harder DLP in the multiplicative subgroup imply harder DLP in the ECC group, and it would come as a surprise that it implied easier DLP in the ECC group.

There are other security reasons. I refer to the first three bullets of the other answer. I get them barely enough to tell they do not lead to a general attack on ECC in $\mathbb F_{2^m}$, e.g. on the curves in section 3 of sec2v2. But still, it's reasonable that they instill uneasiness.

---

In the end, like most, I do accept Safecurve's wisdom :

2006 Bernstein stated that prime fields "have the virtue of minimizing the number of security concerns for elliptic-curve cryptography". Similarly, the Brainpool standard and NSA's Suite B standards require prime fields. There is general agreement that prime fields are the safe, conservative choice for ECC.