Subject: Re: [Cfrg] Complexity of the Microsoft curve proposal

From: Craig Costello <[email-masked]>
Date: Tue, 14 Oct 2014 23:54:11 +0000

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 or Section 3.3 of 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 ends up treating as a generic (large) field element.

All other things being equal, I therefore think that switching between coordinates (if desired) slightly favors p == 3 mod 4. 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 in 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).

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.

Cheers,
Craig

---

From: Michael Hamburg <[email-masked]>
Date: Tue, 14 Oct 2014 18:03:55 -0700

> On Oct 14, 2014, at 4:54 PM, Craig Costello <[email-masked]> 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…

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.

> Craig

Peace,
— Mike

---

From: Watson Ladd <[email-masked]>
Date: Wed, 15 Oct 2014 17:25:25 -0700

On Tue, Oct 14, 2014 at 6:03 PM, Michael Hamburg <[email-masked]> wrote:
> 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
> or Section 3.3 of 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 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
>
> 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 does) or
> of using Mike’s isogeny trick for enhanced
> performance:http://eprint.iacr.org/2014/027.pdf).
>
>

That's exactly right. I want the simplest, fastest, possible solution.
Simplicity matters more because most implementations need to favor
correctness over speed. But speed also matters, to avoid temptation.
So if twisted coordinates are complete, that works great. If not, we
should use untwisted coordinates, so that simple implementations are
secure implementations.

Sadly 2^521-1 is likely to be the prime we need to use for the big
workfactor because of performance/lack of nice primes in that range,
and is 3 (mod 4), so likely untwisted Edwards coordinates will have to
be used for signatures if we want to minimize the number of coordinate
systems used. (The penalty for a performant multiplication with
Edwards coordinates of either twistedness in code size is fairly
large, and the isogeny trick requires implementing arithmetic in the
group order. On the other hand, for signatures this is likely already
needed. In comparison, Montgomery form is very compact in code, even
when performant)

Point compression incurs a slight penalty. However, it entirely
eliminates a class of attacks caused by not checking the order,
provided the square root routine properly checks that the square root
exists. (What happens when a non-quadratic residue is square rooted by
exponentiation or the p=5 (mod 8) method may be exploitable. Yes,
after dividing by i it's a point on the twist, but I don't think
that's what comes out of the formula. And then the addition formulas
aren't right for the twist, so I don't know how to exploit the result
or show it isn't exploitable. However, it's a barrier to exploitation
in any case)

The big advantage of Montgomery coordinates is that they eliminate
entirely validation, so this is a non-issue for ECDH. Sadly, we can't
do signatures with them in a reasonable way, so we're stuck with a
step that might get skipped and cause vulnerabilities when skipped.

>
> 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.dd
>
> This is also why I listed “Curves isogenous to NUMS” as a separate candidate
> from NUMS in the “current candidates” email.

This email, along with the "Curve, Coordinates and Computations" email
is required reading for anyone who wants to understand the issues.
Sadly, I can't find it in my inbox.

Sincerely,
Watson Ladd

--
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Benjamin Black <[email-masked]>
Date: Fri, 17 Oct 2014 16:54:42 -0700

On Tue, Oct 14, 2014 at 6:03 PM, Michael Hamburg <[email-masked]> wrote:

> isogenous.
For the record, my argument was, and is, that _requiring_ implementation of
multiple forms of the same curve is undesirable and unnecessary. At the
time, the discussion was not \w+25519, but X25519 and Ed25519 (and
apologies if I have made mistakes with the various 25519 names). As the
discussion has moved on from there, I don't think it is terribly relevant.

b