[curves] Isogeny patterns among Edwards curves

[Michael Hamburg]

On Jan 30, 2014, at 7:05 PM, Watson Ladd <watsonbladd at gmail.com> wrote:

> Hmm. Not really, because we can always get back P if it is in the
> order q subgroup by
> an exponentiation. But then your canonical decoding is very expensive.

Yes.  There’s surely a way to disambiguate more cheaply, but it surely won’t actually be *cheap*.  Probably you’d have to take another square root and another Legendre symbol.

> I think most protocol designers would like to not think about this issue.

Yeah, I guess that this makes everything slightly uglier.  But the difference of a point of order 2 doesn’t actually matter most of the time; it just means that you have to compare x1y2 = x2y1 instead of two comparisons y1z2 = y2z1, x1z2 = x2z1.

>> 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.
> 
> Signatures usually do.

Yeah, but you usually sign with an Edwards implementation that uses precomputed comb tables, not Montgomery.

> The regular Montgomery ladder can recover y with a few extra muls. If
> we can figure out a class
> of curves/sign bits for which the sign bit of u/v can be computed from
> u and v easily this will be nice.
> Legendre symbol has this property but rules out Curve25519. Perhaps
> when I think about optimization
> in projective coordinates I will figure out a way to batch inverse
> calculations to get the Edwards point on the nose without
> more work then computing XZ^(p-2) ordinarily. In that case we won't
> need any of this: Edwards ladders can recover
> points with very little additional work.

Yeah, you effectively have to decompress the input point, invert the resulting y, and pass through the formula that you get from the ladder with a giant batch inversion / square root operation.  It should work, though I somewhat doubt that it’ll be pretty.  Even with Legendre symbols, the operation takes about a dozen multiplies.

Let me know what you figure out, though.

Cheers,
— Mike

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20140130/b3f7e819/attachment.html>