Re: [Cfrg] Elliptic curve evaluation truths

["Parkinson, Sean" <[e-mail]>]

I can't say I've seen the point addition described in the literature, but always assumed that there are, and I've been assured there are equations.

How about:
4. Signing and verification operations on Montgomery curves is less efficient than on Twisted Edwards and short Weierstrass curves.

Sean
--
Sean Parkinson | Consultant Software Engineer | RSA, The Security Division of EMC
Office [phone] | Fax [phone]
www.rsa.com


-----Original Message-----
From: Cfrg [mailto:[e-mail]] On Behalf Of Parkinson, Sean
Sent: Wednesday, 26 November 2014 10:02 AM
To: Watson Ladd
Cc: [e-mail]
Subject: Re: [Cfrg] Elliptic curve evaluation truths

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