Re: [Cfrg] ECC mod 8^91+5

Hi Dan,

Thanks so much for clarifying this!  

Sorry to all in CFRG that I am not up to speed on ECC implementation security and efficiency.

Just to be clear: this proposed special curve 2y^2=x^3+x (over GF(8^91+5)) is not intended to meet all SafeCurves requirements (as I remember them).  In particular and especially, (a) it is not twist-secure, and (b) it has a special feature of an efficient (complex) endomorphism.

Best regards,

Dan

Dumb question (on efficiency): For plain old Diffie--Hellman, is it right that Edwards form (8M per op) is only better than Montgomery (9M per bit) if a large window is used (to reduce ops/bit to something close to 1)?  If so, is this deemed simpler?  I guess where I'm going with this, is that Edwards form is very exciting from a research perspective, but maybe (0.000001% sure) it is not ready and ideal for engineering.  Again, I'm probably just totally missing something.

-----Original Message-----
From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of D. J. Bernstein
Sent: Wednesday, August 2, 2017 11:25 AM
To: cfrg@irtf.org
Subject: Re: [Cfrg] ECC mod 8^91+5

Ilari Liusvaara writes:
> Unfortunately there is another related problem: The theorem that says 
> that folded Montgomery ladder always works assumes that there is 
> unique point of order 2.

The theorem in the Curve25519 paper assumed a unique point of order 2, but this turned out to be unnecessary. See Theorem 4.5 in

   https://cr.yp.to/papers.html#montladder

and in particular the proofs of the underlying DBL and DADD theorems via the Edwards addition law. The paper also gives proofs from the historical Weierstrass perspective.

The completeness issue is more problematic outside the ladder context:

   * The fast complete Edwards formulas don't apply to this curve: the
     curve doesn't have a unique point of order 2.

   * The fast complete Hessian formulas also don't apply to this curve:
     the curve doesn't have a unique point of order 3.

   * The formulas from https://cr.yp.to/talks/2009.07.17/slides.pdf and
     https://eprint.iacr.org/2015/1060 do apply but don't meet the
     SafeCurves requirements of speed and simplicity ("implementations
     of scalar multiplication for the same curve cannot be much faster"
     and "reasonably fast implementations of scalar multiplication for
     the same curve cannot be much more concise"), so implementors are
     pressured to use incomplete formulas instead.

---Dan

_______________________________________________
Cfrg mailing list
Cfrg@irtf.org
https://www.irtf.org/mailman/listinfo/cfrg