[curves] Isogeny patterns among Edwards curves

[Mike Hamburg]

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.
> 
> Cheers,
> — 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.

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