Re: [Cfrg] Complexity of the Microsoft curve proposal

[Michael Hamburg <[e-mail]>]

> On Oct 14, 2014, at 4:54 PM, Craig Costello <[e-mail]> wrote:
> 
> Hi Watson, 
>  
> To elaborate a little on what Mike said, when p == 3 mod 4, defining searches for twist-secure curves that minimize the absolute value of the Montgomery constant automatically minimize the absolute value of the constant on the isogenous (complete) Edwards curve and the absolute value of the constant on the isogenous twisted Edwards curve. So regardless of whether our curves are implemented using Edwards coordinates, twisted Edwards coordinates, or Montgomery coordinates, the corresponding curve constant will be small (see Section 2 of http://eprint.iacr.org/2014/027.pdf <http://eprint.iacr.org/2014/027.pdf> or Section 3.3 of http://eprint.iacr.org/2014/130.pdf <http://eprint.iacr.org/2014/130.pdf> to see that there is no problem here).
>  
> On the other hand, I’m not sure if this happens when p == 1 mod 4: for example, the Edwards version of Curve25519 has a curve constant that’s a fraction of small numbers, which the implementation documented in http://eprint.iacr.org/2011/368.pdf <http://eprint.iacr.org/2011/368.pdf> ends up treating as a generic (large) field element.

This is because Bernstein et al specified an isomorphic curve and not an isogenous one.  They could have specified the 4-isogenous curve 

x^2 + y^2 = 1 + d x^2 y ^2 where d = (2-A)/4 = -121665.

[
At least if I haven’t made a mistake:
  x = 4v(u^2-1) / ((u^2-1)^2+4v^2)
  y = u (4v^2 - (u^2-1)^2) / (2v^2(u^2+1) - u(u^2-1)^2)

dual:
  u = y^2/x^2
  v = y(x^2+y^2-2)/x^3
]

or the curve

-x^2 + y^2 = 1 - d x^2 y^2

which is isomorphic to that one under the map x -> ix.  Both of these curves are complete, because GF(2^255-16)(+-121665) is nonsquare.

> All other things being equal, I therefore think that switching between coordinates (if desired) slightly favors p == 3 mod 4.

There are advantages to p == 3 mod 4, but I don’t think this is one of them.  Note that p == 1 mod 4 supports curves which are both twisted [a=-1] and complete, but 3 mod 4 does not.  So in terms of coordinate systems, that’s the simplest, fastest option.  You can recover most of that with the isogeny trick, but not all of it.

> Furthermore, in this case, if the curve is defined as an a=1 (complete) Edwards curve, implementers then have the option of staying in Edwards form at the expense of 1 field multiplication per addition operation (like the implementation of Curve41417 inhttp://eprint.iacr.org/2014/526.pdf <http://eprint.iacr.org/2014/526.pdf> does) or of using Mike’s isogeny trick for enhanced performance:http://eprint.iacr.org/2014/027.pdf <http://eprint.iacr.org/2014/027.pdf>).

I think Watson’s points were:
1) If the NUMS curves are chosen, they should be changed to the isogenous untwisted ones.
2) Whatever curves are chosen, they should compress points.

> In any case, this is (as you say) about the coordinates, not the curve. However, changing coordinates can change the corresponding curve constant, but when p == 3 mod 4 small constants will remain small irrespective of the coordinate system.

An isogeny is a bit more than just a change in coordinates, but I agree that it’s reasonable to pick a curve structure, and later discuss which isogenous or isomorphic curves and which coordinates should be used for which protocols.

I don’t think everyone on this list would agree with the above statement, though.  A pretty big part of Benjamin Black’s argument against \w+25519 is the idea that they are different curves, not just different coordinates for the same curve, even though the curves are isomorphic and not just isogenous.

This is also why I listed “Curves isogenous to NUMS” as a separate candidate from NUMS in the “current candidates” email.

> Cheers,
> Craig

Peace,
— Mike