Re: [Cfrg] Elliptic curve evaluation truths

[Michael Hamburg <[e-mail]>]

Usually Montgomery curves are used because they have a very simple and efficient x-only Montgomery ladder implementation, where the y coordinate is not computed, at least not in the inner loop.

It is not possible to add two points without some information about the y-coordinate.  However, if the y-coordinate is given (compressed on the wire, but uncompressed internally), then it possible to add points on a Montgomery curve.  That’s not what people will do, though.  Instead they’ll convert to (twisted) Edwards, where all the math is much simpler.  Depending on the signature form, it may be possible to verify without adding, but people probably won’t do that either.

Likewise, it is possible but not practical to use “pools of points” on a Montgomery curve.  Instead people will use Edwards form.

So I would state:

def) “Twisted Edwards” includes traditional Edwards curves with a = 1.

0) Every Montgomery curve is equivalent (isomorphic) to a Twisted Edwards curve.  Every Twisted Edwards curve is equivalent to a Montgomery or twisted Montgomery curve.  Every elliptic curve is equivalent to a short Weierstrass curve.

4) Signing and verification on a Montgomery curve practically requires using Twisted Edwards form.

6) Twisted Edwards and short Weierstrass curves support precomputed tables to speed up ephemeral DH.  Supporting this for Montgomery curves practically requires using Twisted Edwards form.

Nitpicking Watson’s claims:

Every curve supports the Montgomery ladder, often in several flavors.  Montgomery curves are used because they have a particularly simple and efficient Montgomery ladder.  A curve with a point of order 4 in some other form may have a somewhat slower or more complex Montgomery ladder than Montgomery curves.

Cheers,
— Mike


> On Nov 25, 2014, at 4:02 PM, Parkinson, Sean <[e-mail]> wrote:
> 
> My understanding is that because you can't efficiently perform a point add operation of two random points with Montgomery curves then signature schemes are out.
> Is there inefficient algorithms for performing point add on the Montgomery curve?
> I intended to not include transforming points to other curve types. So maybe,
>  4. Signing and verification operations on Montgomery curves is not possible.
> 
> I'm intentionally not talking about simplicity of implementations. That is making things more complicated and hiding the 'truths'.
> 
> Sorry, 'Pools of points' was my name for the technique of having a number of pre-generated points that are then added to each other to quickly generate new points for TLS PFS.
> 
> 
> Sean
> --
> Sean Parkinson | Consultant Software Engineer | RSA, The Security Division of EMC
> Office [phone] | Fax [phone]
> www.rsa.com
> 
> 
> -----Original Message-----
> From: Watson Ladd [mailto:[e-mail]] 
> Sent: Wednesday, 26 November 2014 2:35 AM
> To: Parkinson, Sean
> Cc: [e-mail]
> Subject: Re: [Cfrg] Elliptic curve evaluation truths
> 
> On Mon, Nov 24, 2014 at 11:56 PM, Parkinson, Sean <[e-mail]> wrote:
>> In hopes of reaching consensus, I thought I might start a list of 
>> known truths.
>> 
>> Please don’t just argue against each point but instead look to refine 
>> the statements where possible.
>> 
>> 
>> 
>> 1.       Only curves over prime fields are being considered.
>> 
>> 2.       Good, efficient implementations of Twisted Edwards curves will
>> faster than good, efficient implementations of short Weierstrass with 
>> the same prime.
>> 
>> 3.       Good, efficient Montgomery curve implementations are simpler than
>> good, efficient Twisted Edwards and short Weierstrass curve implementations.
>> 
>> 4.       Montgomery curves cannot be used for signing/verification
>> operations.
> 
> This is incorrect: see DJB's "Curves, Coordinates and Computation emails". One can retrieve y-coordinates from the Montgomery ladder.
> In fact, 2 and 3 both need to be reworked in light of this email.
> 
> The correct statement is that curves with a complete addition law are easy to work with, and that the Montgomery ladder is also very simple.
> Curves have a complete addition law if they are isomorphic to Edwards curves, which is almost the same as having a point of order 4. The Montgomery ladder works for curves with a point of order 4. (I may have gotten the conditions somewhat wrong: this is morally correct)
> 
> How the curve is presented on the wire doesn't change this: one does a few fast calculations to put the point retrieved from the wire in the preferred form for calculation, and a few fast ones at the end to put it back in the form on the wire.
> 
> This is also missing security considerations: it's easy to get multiplication correct with a complete addition law, much harder without one. Edwards curves always have a complete addition law, while Twisted Edwards may or may not, depending on the value $a$ being a quadratic residue or not.
> 
>> 
>> 5.       Small co-factor curves are no weaker, in terms of small subgroup
>> attacks, than co-factor 1 curves.
>> 
>> 6.       Twisted Edwards and short Weierstrass but not Montgomery curves
>> support pools of points for ephemeral DH.
> 
> What do you mean by pools of points? Do you mean fast fixed-based exponentiation? In that case one can do a fast fixed-based exponentiation on the isomorphic or isogenous Edwards curve, and use a few fast computations to get the point on the Montgomery curve.
> 
>> 
>> 7.       NIST curves are going to be in use for some time.
>> 
>> 8.       One curve at about WF-128 is required.
>> 
>> 9.       At least one curve with WF greater than 128 is required.
>> 
>> 10.   Good, efficient implementations of curves using special primes are
>> significantly faster than good, efficient implementations using random 
>> primes.
>> 
>> 11.   There are steps in performance based on the number of words used.
>> 
>> 12.   There are a few special primes that are significantly faster than the
>> step they are on.
>> 
>> 13.   The curves chosen will be used for ECDH and ECDSA.
>> 
>> 14.   The curves will be used in TLS and certificates.
>> 
>> 
>> 
>> If you have more truths then please add to this list.
>> 
>> 
>> Sean
>> 
>> --
>> 
>> Sean Parkinson | Consultant Software Engineer | RSA, The Security 
>> Division of EMC
>> 
>> Office [phone] | Fax [phone]
>> 
>> www.rsa.com
>> 
>> 
>> 
>> 
>> _______________________________________________
>> Cfrg mailing list
>> [e-mail]
>> http://www.irtf.org/mailman/listinfo/cfrg
>> 
> 
> 
> 
> --
> "Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither  Liberty nor Safety."
> -- Benjamin Franklin
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg