On Jan 29, 2014, at 6:56 PM, Michael Hamburg <[email protected]> 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
_______________________________________________
Curves mailing list
[email protected]
https://moderncrypto.org/mailman/listinfo/curves
