[curves] Isogeny patterns among Edwards curves

[Mike Hamburg]

On Jan 30, 2014, at 10:05 PM, Robert Ransom <rransom.8774 at gmail.com> wrote:

> On 1/30/14, Michael Hamburg <mike at shiftleft.org> wrote:
> 
> Just to clarify: the following paragraph is Watson Ladd's.  (You
> didn't quote anything that I wrote in this message.)

Sorry about that.

>>> I think any encoding should be able to represent the entire curve,
>>> without nasty problems like this.
>> 
>> Aside from performance concerns, do you think it’s actually a problem if the
>> encoding fails to faithfully convey points, by destroying the difference
>> between P and P+(point of order 2)?
> 
> It destroys the difference between P and Phi+P, where Phi is a
> non-rational point and can't be represented in any other format that
> has been discussed.

No, this is the rational point (0,-1) of order 2.  It also destroys the difference between P and Phi-P, which is fine because Phi-P is not rational.

>> What this has vs a coordinate+signbit compressed Edwards point is that you
>> can use the Montgomery ladder without destroying the sign bit, and without
>> paying more than a few muls extra to compute it.  This is nice for a
>> protocol which wants to do a scalar mul but cares about the sign that comes
>> out afterwards.  Dragonfly does exactly this.  I know that neither of us
>> loves Dragonfly, but there may be other protocols that care about this sort
>> of thing.
> 
> This benefit seems relevant to SPAKE2 as well.

Possibly.  A lot of these protocols you'd use Edwards for anyway though.  For SPAKE2, you have to add before doing the scalarmul, which decreases the benefit.

>> What’s more, this is the first suggestion for a unified point format which
>> might reduce complexity instead of increasing it.  But only if I can work
>> out a nice decompression algorithm.
> 
> You've probably noticed this already, but someone should say it
> anyway: this is exactly the same format as your earlier proposal to
> send 1/sqrt(u), but now you've found out how to avoid computing a
> square root during encoding (as well as other clear benefits).

This is 1/sqrt(u) to be sure, but it's not the same format I proposed before.  The earlier 1/sqrt(u) format was on a different curve (an isomorphic one, not an isogenous one), and it had a different sign bit (the Legendre symbol of v or y).  The old trick is actually faster in most cases, and more flexible (no odd-power restriction).  But it's also much more complicated, especially for the Montgomery ladder.  In the Legendre symbol version, it also only works for p == 3 mod 4, and the low-bit version is probably very messy.

I'm still sort of hoping to improve one of these tricks to where it can be clearly worthwhile as a universal format, partly because I really like the elegance of 1-coordinate point formats.  But I still think that right now they're a bit unwieldy, so I can't claim that they're better than the coordinate+signbit yet.

Anyway, work continues, though I think I'll go back to implementation for a while.  There are lots of things to try, and only so much time in the day...

My coworker Mark likens this sort of exercise to squeezing a water balloon.  You can change the shape, but you can't reduce the volume :-/

Cheers,
-- Mike