On Thu, Jan 30, 2014 at 9:08 AM, Robert Ransom <[email protected]> wrote: > 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.
There is also a bigger problem: each encoding and decoding doubles the point. This is fine for ECDH, but makes signatures ugly. I think any encoding should be able to represent the entire curve, without nasty problems like this. Yes, it's surmountable, but what does this idea have over a regularly compressed Edwards point? > > > Robert Ransom > _______________________________________________ > Curves mailing list > [email protected] > https://moderncrypto.org/mailman/listinfo/curves -- "Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither Liberty nor Safety." -- Benjamin Franklin _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
