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

Hi Ilari,

Thank you very much for taking a look at these important details: I've been focusing on other aspects.

I did not know about the condition on uniqueness of a point of order 2.  So, I will try to better learn this important implementation issue.  If you happen to know off-hand a reference to the theorem you cited, then please let me know - but don't sweat it, I'll eventually find it (99% sure).

I did not understand what you meant by the "worst problem" being a "notation" for low-order points.   (My only guess (1% sure) is that "notation" could be some kind of "exception"?)  Also, I'm assuming that "worst" is in some relative sense, since Curve25519 has low-order points.  Also, is your implied assertion that "a complete curve has low-order point" a theorem?  (I had mistakenly thought complete formulas for NIST had been found, albeit slower - maybe they were only unified, so my understanding of what "complete" means is off.)

In my slides, I mentioned that the propose curve's cofactor (72) not being a power of 2 is problematic for easily generating signature ephemerals without bias. This has some known workarounds, but it is a serious issue.  Did you have something else in mind in saying that a subgroup of order 9 was problematic?

-----Original Message-----
From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Ilari Liusvaara
Sent: Wednesday, August 2, 2017 4:13 AM
To: Dan Brown <danibrown@blackberry.com>
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] ECC mod 8^91+5

On Tue, Aug 01, 2017 at 09:22:10PM +0000, Dan Brown wrote:
> Hi CFRG,
> 
> A minor addition to this topic.
> 
> In my first email on this topic, and in my recent IETF 99 
> presentation, I mentioned that the proposed special curve 2y^2=x^3+x 
> was similar to curves proposed in Miller's 1985 paper introducing of 
> ECC.
> 
> I believe (50% sure) that Miller made this non-square a recommendation 
> merely to help keep the group cofactor down (by ensuring a unique 
> point of order 2, namely (0,0)).

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.

So if using curve with multiple points of order 2, there may be exceptional cases. And getting those cases wrong might be exploitable.

And handling those cases without timing sidechannels might be very nasty to implement.

And sets of complete Montgomery and complete Edwards curves are very closely related, so this is probably not complete either as Edwards curve.

> By contrast 2y^2=x^3+x, has a subgroup of order 8.  (With points O, 
> (0,0), (i,0), (-i,0), (1,1), (1,-1), (-1,i), (-1,-i).)  A subgroup  of 
> order 4 (or 8) is nowadays considered (arguably) an advantage, because 
> of various Edwards curves (but I am only 10% sure, since I haven't 
> looked at this in a while, please correct me this is wrong).

It also seemingly has subgroup of order 9, which is considerably more problematic than subgroup of order 8.

There are some more exotic ECC algorithms that just can't deal with cofactor bigger than 1, but I think the worst problems that are attributed to cofactor >1 are actually caused by having a notation for low-order points. And any complete curve has at least one such point.

And then, not having notations for low-order points is annoying in implementing algorithms...

-Ilari

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