[curves] Isogeny patterns among Edwards curves
mike at shiftleft.org
Thu Jan 30 23:34:14 PST 2014
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 :-/
More information about the Curves