On 1/30/14, Mike Hamburg <[email protected]> wrote: > 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.
> 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. Now I really get it. Let t=x/y denote a compressed point on a*x^2 + y^2 = 1 + d*x^2*y^2, where a=1. The curve equation can be rearranged into the form d*x^4 - x^2*(1 + a*t^2) + t^2 = 0; substitute w=x^2 and solve for w using the quadratic formula. The quadratic formula produces two possible values of w. One is x^2; the other solution turns out to be 1/(d*y^2) (the square of the x coordinate of Phi+(x,y)). So w is the x^2 value for *one* of the two points which compress to t=x/y over the algebraic closure Fbar; it's either P or Phi-P. The Legendre symbol test is necessary to determine which w is indeed x^2 for some x (and thus is P). If it is omitted, decompression could apply the isogeny to Phi-P instead, which eliminates Phi and produces -P instead of P (thus wiping out the nice feature of preserving the sign bit). I'm also not seeing a workaround for this. Robert Ransom _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
