On Thu, Jan 30, 2014 at 1:37 PM, Michael Hamburg <[email protected]> wrote: > > > On Jan 30, 2014, at 11:38 AM, Watson Ladd <[email protected]> wrote: > > On Thu, Jan 30, 2014 at 9:08 AM, Robert Ransom <[email protected]> > wrote: > There is also a bigger problem: each encoding and decoding doubles the > point. This is fine for ECDH, but makes signatures ugly. > > > At worst you can recover P or P+(point of order 2) with two square roots, > effectively backing out of the isogeny rather than completing it. This > might be more expensive than decompressing and doubling, but it’s not > horrible. Since you’re going to check the equation (r*G + s*PubKey) ?= > NoncePoint, the recipient only has to decompress the public key, not the > NoncePoint. After compressing, they can check the equation with no > expensive ops, because they’ll have have an Edwards point as (xz,yz,z) and > the NoncePoint is supposed to be x/y = xz/yz. > > If the PubKey is a q-torsion point, which it should be, you could instead > check r*G + (s/4 mod q)*4*PubKey ?= NoncePoint. The fastest implementations > will do something like that anyway using the isogeny to the twisted Edwards > curve E(-1,d-1), since that’s about 5% faster and has slightly simpler > formulas.
Hmm. Looking at Ed25519 paper again, what we can do is send R as a point and S as usual, then have the verify complete the 4-isogney and double instead of square. This works for batch verification as well. > > Compare this to a coordinate+signbit encoding, where to check the sign bit > (not suuuuuper necessary, but a good idea for strictness) you have to do a > division at the end. Or if the sign bit is a Legendre symbol, you have to > compute that symbol. So in total, signature checking is not much more > complicated or expensive with the x/y encoding than it is with > coordinate+signbit. > > But you’re right, it’s not all pretty. If I can’t find a way to avoid the > extra square root or Legendre symbol, then it will be more expensive for > batch verification. For that, you can check 4*r*G + s*4*PubKey ?= > 4*NoncePoint. So it doesn’t hurt that the points get doubled or quadded by > the cheaper version of decompression. > > Likewise, in the Elligator PAKE, you have to compute wire+elligator, and > eventually serialize to wire again, which (as things stand) costs at least 1 > square root, 1 Legendre and 1 inversion in addition to the elligator and the > scalarmul. This is compared to just a square root and an inversion for a > coordinate+signbit representation. > > So, maybe it's not good enough *yet*, because it adds moderate slowdowns to > batch-verify and Elligator PAKE. But it doesn’t really slow down ECDH, > signing or single-verify, which is pretty good for a trick I’ve been working > on since yesterday. > > 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)? 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. I think most protocol designers would like to not think about this issue. > > Yes, it's surmountable, but what > does this idea have over a regularly compressed Edwards point? > > > 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. 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. > > 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. > > Also, it might dodge patents, but that probably doesn’t matter if the > patents are expiring in July anyway. > > Cheers, > — Mike > -- "Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither Liberty nor Safety." -- Benjamin Franklin _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
