[curves] Fwd: Climbing the elliptic learning curve (was: Finalizing XEdDSA)

[AA EE]

(Hopefully I've managed to re-subscribe myself- too many e-mail addresses). Without equations, maybe it's not quite clear why the degree 'drops' in that intuition (and the typical Edward's ones can be hard to picture in your head). Try the curve y^2 = x^3. This is singular by computing the jacobian (2f/2y, 2f/2x) at (0,0). Apply the substitution y = x*t (so increasing the number of variables, as we look in a new direction). This will give you x^2t^2 = x^3 or x^2(t^2-x) the new curve is t^2 - x (which is a smooth parabola, and a degree lower) and the x^2 term represents the singular point, expanded into a double line which we ignore. Unfortunately the references I can think of all seem to start from a heavy commutative algebra perspective rather than crypto, and might be sort of off-putting...

> Sent: Thursday, November 03, 2016 at 7:46 PM
> From: "Andrew Egbert" <backuntri at gmail.com>
> To: divbit at mail.com
> Subject: Fwd: [curves] Climbing the elliptic learning curve (was: Re: Finalizing XEdDSA)
>
> 
> 
> > Begin forwarded message:
> > 
> > From: Ron Garret <ron at flownet.com>
> > Subject: Re: [curves] Climbing the elliptic learning curve (was: Re: Finalizing XEdDSA)
> > Date: November 3, 2016 at 2:07:42 PM PDT
> > To: Andrew Egbert <backuntri at gmail.com>
> > Cc: curves at moderncrypto.org
> > 
> > [cc’ing the list at Andrew’s suggestion]
> > 
> > Thanks!  That is exactly the kind of explanation I was looking for.  (Thanks also to Robert Ransom who also responded off-list.)
> > 
> > On Nov 3, 2016, at 1:54 PM, Andrew Egbert <backuntri at gmail.com> wrote:
> > 
> >> Ah- must have unsubscribed or something (feel free to post this to the list). I can try to explain intuitively whats happening, and why the degree of the polynomial decreases. 
> >> Imagine you have a curve of some sort in 2-dimensions, this will be an equation with x, y (two variables). Now imagine you look at the curve in three dimensions.
> >> If it really is still a one-dimensional object, it will need to have 3 variables (otherwise it will be a surface if ‘z’ is not specified).  
> >> 
> >> Resolving singularities of curves is often (not always) a similar process. Imagine you have a curve with a ‘cusp’ which is sort of like a sharp ‘singular’ point.
> >> (You can google image search plane curve cusp to get an idea)
> >> Now imagine that instead of a sharp point, you are actually looking at a place where the curve is going ‘downwards’ in a third dimension (so in fact it is a smooth curve).
> >> This is sort of what’s happening. 
> >> Best, 
> >> Andrew
> >> 
> >>> On Nov 3, 2016, at 1:48 PM, Ron Garret <ron at flownet.com> wrote:
> >>> 
> >>> Not sure what “bad response” you’re referring to here because this is the only message I’ve received from you.  I took a look at page 1, and I do understand the change of variables that transforms curve25519 into Ed25519 and vice-versa.  It’s the more general case that I don’t yet fully understand.
> >>> 
> >>> I have a working theory though: because the transformation involves a change of variables, the letters X and Y have completely different semantics in the Edwards formula than in the other forms.
> >>> 
> >>> On Nov 3, 2016, at 1:36 PM, Andrew Egbert <backuntri at gmail.com> wrote:
> >>> 
> >>>> Sorry that was a bad response, since I missed the last sentence of your post- I’ve written out the transformation on page 1 of my thesis here: https://divisibility.files.wordpress.com/2016/02/thesismarch18.pdf (also available at my github)
> >>>>> On Nov 3, 2016, at 12:30 PM, Ron Garret <ron at flownet.com> wrote:
> >>>>> 
> >>>>> 
> >>>>> On Nov 1, 2016, at 2:40 PM, Trevor Perrin <trevp at trevp.net> wrote:
> >>>>> 
> >>>>>> It would be be great if there were better surveys on modern ECC and
> >>>>>> engineering issues.  If someone wanted to suggest a reading list /
> >>>>>> bibliography that would be a nice contribution (but also a bunch of
> >>>>>> work).
> >>>>> 
> >>>>> I decided it would be a useful exercise for me to undertake to write such a survey (even if I couldn’t actually finish it), and right away I ran into a snag.  I was trying to reconcile all the different forms of elliptic curve formulas commonly found in the literature, and found the following promising-looking lead on mathworld:
> >>>>> 
> >>>>> http://mathworld.wolfram.com/EllipticCurve.html
> >>>>> 
> >>>>> Ax^3 + Bx^2y + Cxy^2 + Dy^3 + Ex^2 + Fxy + Gy^2 + hHx + Iy + J = 0
> >>>>> 
> >>>>> This is consistent (AFAICT) with the definition given in section 4.4.2.a of Cohen and Frey.  But then there are Edwards curves, which have a x^2y^2 term in them.  How do those fit in?
> >>>>> 
> >>>>> In fact, as I started thinking about this I realized that Edwards curves are really weird because they’re quartic and not cubic (aren’t they?) and all elliptic curves are supposed to be cubic (aren’t they?)  How can a fourth-order polynomial be birationally equivalent to a third-order polynomial?
> >>>>> 
> >>>>> I tried taking a look at some of the proofs that Edwards curves are birationally equivalent to Montgomery curves but they went way over my head.  Is there a more elementary way of understanding this?
> >>>>> 
> >>>>> Thanks,
> >>>>> rg
> >>>>> 
> >>>>> _______________________________________________
> >>>>> Curves mailing list
> >>>>> Curves at moderncrypto.org
> >>>>> https://moderncrypto.org/mailman/listinfo/curves
> >>>> 
> >>> 
> >> 
> > 
> 
>