[curves] Isogeny patterns among Edwards curves
mike at shiftleft.org
Thu Jan 30 01:30:37 PST 2014
On Jan 29, 2014, at 6:56 PM, Michael Hamburg <mike at shiftleft.org> wrote:
> Apparently the 4-isogeny is
> (x,y) -> (y^2/x^2, y(x^2+y^2-2)/x^3)
> from Ed(d): x^2 + y^2 = 1 + d x^2 y^2
> to Mont(2-4d) : y^2 = x(x^2 + (2-4d)x + 1)
> in which (A-2)/4 = -d, or (A+2)/4 = 1-d.
> — Mike
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!
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:
da = (u1-z1)(u2+z2)
cb = (u2-z2)(u1+z1)
x3 = (da+cb)^2 * enc^2
z3 = (da-cb)^2
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.
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.
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.
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.
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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Curves