On Jan 30, 2014, at 10:05 PM, Robert Ransom <[email protected]> wrote:
> On 1/30/14, Michael Hamburg <[email protected]> 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 _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
