<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;"><div><br></div><br><div><div>On Jan 29, 2014, at 6:56 PM, Michael Hamburg <<a href="mailto:mike@shiftleft.org">mike@shiftleft.org</a>> wrote:</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;">Apparently the 4-isogeny is<br><br>(x,y) -> (y^2/x^2, y(x^2+y^2-2)/x^3)<br><br>from Ed(d): x^2 + y^2 = 1 + d x^2 y^2<br>to Mont(2-4d) : y^2 = x(x^2 + (2-4d)x + 1)<br><br>in which (A-2)/4 = -d, or (A+2)/4 = 1-d.<br><br>Cheers,<br>— Mike<br></div></blockquote><br></div><div>I just noticed a really weird corollary to this, which might lead to the One True Point Format. Or maybe not, but follow along. If you compress points from Edwards as y/x (or as x/y to allow the identity to be encoded), then the resulting points can be Montgomery laddered... but only by odd scalars!</div><div><br></div><div>Why's that? Let P in M have the Montgomery ladder coordinates (u,v) where u0 = y^2/x^2 and v is unknown. P is encoded as enc := x/y, from which 1/u0 can computed by squaring. To raise P to the 2s+1, let Q = sP using the Montgomery ladder. The Montgomery ladder now holds P, Q=(u1:?:z1), P+Q=(u2:?:z2). Now do half of another ladder step to compute P+2Q = (2s+1)P:</div><div><br></div><div>da = (u1-z1)(u2+z2)</div><div>cb = (u2-z2)(u1+z1)</div><div><br></div><div>x3 = (da+cb)^2 * enc^2</div><div>z3 = (da-cb)^2</div><div><br></div><div>From this, the encoded output is seen to be (da+cb) * enc / (da-cb). It's not obvious that the sign is correct, but testing says that it is (needs a proof). In total, this changes the Montgomery ladder to preserve the sign and use a unified format at a cost of 3M+S+6add, which I think is pretty cheap. Compression costs an additional 1M compared to just dropping the x-coordinate, which again is cheap.</div><div><br></div><div>It's not possible to do this trick with even scalars. This is because there's an "imaginary infinite point of order 2", Phi = (infinity, 1/sqrt(d)) on E(P2(Fbar)). It's not in E(P2(F)) when d is not square. We have Phi+(x,y) = (1/ysqrtd, -1/xsqrtd), which encodes as -enc, just like -P does. In other words, it's not possible to distinguish between P and Phi-P. When multiplied by an even scalar, the Phi cancels out, so you wouldn't be able to distinguish between P and -P. This is over Fbar, but you can't tell F from Fbar without eg taking roots.</div><div><br></div><div>When the cofactor is 4, I believe that there's no security concern in forcing the exponent to be odd, i.e. in letting s be in [1,q-1] where q is the prime part of the order. This is because the x-coordinate of P is square, which in turn means that P=2R for some point R. Thus (2s+1)P = (4s+2)R, which has the same cofactor component as P, regardless of what S is. Thus, if the input has a 2-torsion component then so does the output, regardless of S. Likewise, if the cofactor is 8, then you should raise to the 4s+1 instead of the 2s+1.</div><div><br></div><div>I tested this, and it works. I think it works for the twist, too, but it needs more testing (my quick test tonight *does* break for the twist, but that's because it's using Edwards to learn ground truth). I tested in a field which was -1 mod 4, but it should work in a field which is 1 mod 4, since I'm not using Legendre symbols anywhere. Again, I could be wrong.</div><div><br></div><div>This issue of decompression to Edwards remains, and this is not cheap: it costs 2 square roots instead of 1, or at least a square root and a Legendre symbol check (even when p==1 mod 4: the criterion is that d has to be nonsquare). I'm looking for a way to fix this now, but I'm not sure there is one.</div><div><br></div><div>Cheers,</div><div>-- Mike</div></body></html>