Re: [Cfrg] Elliptic curve evaluation truths

[Watson Ladd <[e-mail]>]

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