3
$\begingroup$

I recentely had a discussion about the redesign of our ECC code for the library I'm collaborating on and the person I was discussing with came up with Edwards and Montgomery curves over binary extension fields. I suspect he just did this because "why not?" as it seems to be straight conclusion to think they exist for the binary case and they are special for the prime field case.

This made me think and look into the addition law for Edwards curves over prime fields and it looks like you can't trivially do this over binary extensions fields.

So I had the following questions regarding (twisted) Edwards / Montgomery curves over binary extension fields:

  1. Do they exist?
  2. Are they any special, like Curve25519 and Curve448 are (i.e. easy side-channel resistant implementation)?
  3. Are there standardized curves for them?

I suspect 1) to tell me "yes", because these curves can theoretically normally defined via the equations. I don't know about 2) but suspect they aren't special (or I would have heard of them) due to the vastly different implementation of the underlying field arithmetic between the prime and binary case. I doubt 3) holds, but I may have just missed them.

$\endgroup$
1
$\begingroup$

So I had the following questions regarding (twisted) Edwards / Montgomery curves over binary extension fields:

  1. Do they exist?

Yes[1]. They have the form $$d_1 (x + y) + d_2 (x^2 + y^2) = x y (1 + x) (1 + y)$$ where $d^2 \ne {d_1}^2 + d_1$. The identity is $(0, 0)$; negation sends $(x, y) \mapsto (y, x)$. If $d_2 \ne \alpha^2 + \alpha$ for any $\alpha$, then like (nonbinary—represent!) Edwards curves, binary Edwards curves have a relatively simple complete addition law, detailed in the EFD.

  1. Are they any special, like Curve25519 and Curve448 are (i.e. easy side-channel resistant implementation)?

BBE251[2] is the binary Edwards curve over the field $\mathbb F_2[t]/(t^{251} + t^7 + t^4 + t^2 + 1)$ with coefficients $$d_1 = d_2 = t^{57} + t^{54} + t^{44} + 1.$$ Like Ed448-Goldilocks, BBE251 was chosen to optimize certain performance metrics within this shape, subject to security constraints detailed in the paper; for example, the small Hamming weight and convenient shape of the polynomial $t^{251} + t^7 + t^4 + t^2 + 1$ makes reduction cheaper, and the small degree and Hamming weight of $t^{57} + t^{54} + t^{44} + 1$ makes multiplication cheaper.

The accompanying software computes a batch of thousands of scalar multiplications in somewhat fewer cycles per key on average than contemporary software for elliptic curves over prime fields of similar conjectured security levels. Even though software doesn't make fast binary field arithmetic easy, the simple complete addition laws make for easy bit slicing in batch computation.

(Side note: There's nothing particularly special about Curve25519 and Curve448 among Montgomery curves over nicely shaped prime fields that makes them encourage side channel resistance. Their equations $y^2 = x^3 + A x^2 + x$ have small coefficients $A$, which makes for a cheaper ladder, but that's a performance optimization, not a security concern. Their primes $2^{255} - 19$ and $2^{448} - 2^{224} - 1$ make for fast constant-time reduction algorithms, but it's not clear that there's any security analogy here when the premise is a bit-sliced batch algorithm anyway.)

  1. Are there standardized curves for them?

Not to my knowledge.

There has been relatively little interest in these curves, it seems, perhaps in part because without a batch advantage they are extremely slow to compute in constant-time software, and perhaps in part because the security of binary field curves seems shakier and not as well-understood—or at least not as confidently understood—as large prime field curves[3].

More recent performance results like [4] are heavily dependent on CPU support for binary field arithmetic, and even then it's not clear that binary Edwards curves are competitive in performance with other alternatives, particularly alternatives that take advantage of fast endomorphisms.

$\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.