[curves] Isogeny patterns among Edwards curves

[Watson Ladd]

On Thu, Jan 30, 2014 at 9:08 AM, Robert Ransom <rransom.8774 at gmail.com> wrote:
> 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.

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
> Curves at moderncrypto.org
> 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