<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><br><div><div>On Jan 30, 2014, at 7:05 PM, Watson Ladd <<a href="mailto:watsonbladd@gmail.com">watsonbladd@gmail.com</a>> wrote:</div><div><br></div><blockquote type="cite"><div style="font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">Hmm. Not really, because we can always get back P if it is in the<br>order q subgroup by<br>an exponentiation. But then your canonical decoding is very expensive.</div></blockquote><div><br></div><div>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.</div><br><blockquote type="cite"><div style="font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">I think most protocol designers would like to not think about this issue.<br></div></blockquote><div><br></div><div>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.</div><div><br></div><blockquote type="cite"><div style="font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><blockquote type="cite">What this has vs a coordinate+signbit compressed Edwards point is that you<br>can use the Montgomery ladder without destroying the sign bit, and without<br>paying more than a few muls extra to compute it. This is nice for a<br>protocol which wants to do a scalar mul but cares about the sign that comes<br>out afterwards. Dragonfly does exactly this. I know that neither of us<br>loves Dragonfly, but there may be other protocols that care about this sort<br>of thing.<br></blockquote><br>Signatures usually do.<br></div></blockquote><div><br></div><div>Yeah, but you usually sign with an Edwards implementation that uses precomputed comb tables, not Montgomery.</div><br><blockquote type="cite"><div style="font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">The regular Montgomery ladder can recover y with a few extra muls. If<br>we can figure out a class<br>of curves/sign bits for which the sign bit of u/v can be computed from<br>u and v easily this will be nice.<br>Legendre symbol has this property but rules out Curve25519. Perhaps<br>when I think about optimization<br>in projective coordinates I will figure out a way to batch inverse<br>calculations to get the Edwards point on the nose without<br>more work then computing XZ^(p-2) ordinarily. In that case we won't<br>need any of this: Edwards ladders can recover<br>points with very little additional work.<br></div></blockquote><div><br></div><div>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.</div><div><br></div><div>Let me know what you figure out, though.</div><div><br></div><div>Cheers,</div><div>— Mike</div><div><br></div></div></body></html>