1
$\begingroup$

In which scenarios we go for prime fields or binary fields? Please indicate why we would choose one over the other.

$\endgroup$
  • $\begingroup$ I think binary fields are better for performance. Can't say as far as security. $\endgroup$ – marshal craft Feb 6 '17 at 11:14
  • 1
    $\begingroup$ @marshalcraft Historically, some curves over extension fields were broken (severely) which is why people tend to be cautious about them. $\endgroup$ – SEJPM Feb 6 '17 at 12:21
  • $\begingroup$ I think that the text in the body of the question is on topic while the title was large and almost off topic. So I changed both somewhat to make the Q even more on topic. Please roll back if you think it changed too mcuh. $\endgroup$ – Maarten Bodewes Feb 6 '17 at 16:49
4
$\begingroup$

Binary fields were developed since they yield more efficient implementations. This is especially true given the Intel PCLMULQDQ instruction. Note, that there are special types of Binary fields that are even more efficient, like Koblitz curves.

However, in general, our confidence in the security of these curves is less than for prime-field curves. Thus, in general, my preference is to use prime-field curves unless there's a special reason why not to.

$\endgroup$
  • 1
    $\begingroup$ I knew that there is an improvement of index calculus over $GF(2^{n})$ (in general for small characteristic fields) . But didn't know that something similar holds for the elliptic curves. Can you elaborate a little? $\endgroup$ – 111 Feb 6 '17 at 16:32
  • $\begingroup$ You need to compute field operations. With carry-less multiply, this can be made much more efficient. See intel.com/content/dam/www/public/us/en/documents/white-papers/…. $\endgroup$ – Yehuda Lindell Feb 6 '17 at 17:12
  • $\begingroup$ maybe I wasn't clear, my question concerns the following : our confidence in the security of these curves is less than for prime-field curves, why we have more confidence (from the security point of view) to elliptic curves defined over a prime field? $\endgroup$ – 111 Feb 6 '17 at 17:24
  • $\begingroup$ There are no successful practical attacks, but there are things being done that are of interest, specifically for the binary field case. I am not an expert on this topic, but my opinion is based on Nigel Smart's opinion, and I consider him a very big expert. You can also look around and find things like ellipticnews.wordpress.com/2015/04/13/… that point to this (no practical attack, but some roadway). $\endgroup$ – Yehuda Lindell Feb 6 '17 at 17:33
  • $\begingroup$ Thanks for the quick reply. Yes, I know the paper of Semaev and indeed it seems impractical as explained in the blog. I was hoping for some other reference. $\endgroup$ – 111 Feb 6 '17 at 17:49
0
$\begingroup$
  • Binary fields require only xor and shift operations to implement (i.e. no multiplications), and thus are faster in many platforms;
  • For the same reason, they are easier to make their implementations resistant to timing attacks (i.e. no need to handle carries);
  • For the same reason, are easier to implement in hardware;
  • Some processors have support for binary polynomial multiplication to use with GCM (e.g. Intel PCLMULQDQ; ARM PMULL), and this can be used for binary ECC too, making it even faster.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.