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

[Ilari Liusvaara <[e-mail]>]

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