[curves] Isogeny patterns among Edwards curves

[Robert Ransom]

On 1/30/14, Mike Hamburg <mike at shiftleft.org> 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