Re: [Cfrg] Proposed requirements for curve candidate evaluation

Hey Mike,

Good question, I’ll explain the difference between the “ed-521-mers” curve and E-521.

Over any chosen prime field, we searched for the twisted Edwards curve E:–x^2+y^2=1+d*x^2*y^2 with smallest *positive* d such that #E<#E’, where E’ is the quadratic twist of E. Many of our chosen primes in the preprint are 64-bit aligned, so we always take E to be the twist with the positive trace; enforcing that means that #E is also 64-bit aligned. The reason we want the smaller sized twist to correspond to the small positive d is that we wanted our implementations to be modular across different security levels – we wanted the formulas to take advantage of the “smallness” of d without worrying about its sign, so our condition became the smallest d>0 such that tr(E)>0 and both twists have cofactor 4. 

The condition d>0 with tr(E)>0 was something we decided on when working on modular implementations for the 6 NUMS curves in the MSR ECCLib release, where we also decided it was best to focus only on the twisted Edwards form of cofactor 4 curves. Originally, when we were also researching the performance of the Montgomery form, our searches prioritized curves with the smallest Montgomery constant (A+2)/4 without caring which twist it was on, so you will notice that in Table 2 of the first version of our preprint (eprint.iacr.org/2014/130 – posted Feb 24th), the curve “ed-521-mers” is presented in Montgomery form y^2=x^3+A*x^2+x with A=1504058. This original curve is isogenous to E-521 (Section 3.3 of our latest preprint shows why the smallest constants coincide when p==3 mod 4), but its twisted Edwards form has the negative d, so we had to search a little higher to satisfy the d>0 requirement. 

Cheers,
Craig

-----Original Message-----
From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Michael Hamburg
Sent: Thursday, August 7, 2014 6:24 PM
To: Watson Ladd
Cc: cfrg@ietf.org
Subject: Re: [Cfrg] Proposed requirements for curve candidate evaluation

> On Aug 7, 2014, at 6:03 PM, Watson Ladd <watsonbladd@gmail.com> wrote:
> 
> E-521 was discovered by three groups independently. There are not that 
> many primes near a power of two, and not that many choices of curve 
> shape. How would we make the process "more rigid?”

On a related note, Brian, do you know why E-521 (or rather, a curve isogenous to E-521 or its twist) isn’t the Microsoft ed-521-mers curve?  Is there something simple I’m missing here?  It seems like that gives a smaller d0 coefficient than the one you chose.

— Mike
_______________________________________________
Cfrg mailing list
Cfrg@irtf.org
http://www.irtf.org/mailman/listinfo/cfrg