Re: [Cfrg] Preliminary disclosure on twist security ...

[Dan Brown <[e-mail]>]

> -----Original Message-----
> From: Watson Ladd
> >
> > Let F_p be the underlying field.
> >
> > Let E be the twist-secure curve, with size #E(F_p) = hr, where h is a 
> > small
> cofactor and r a large prime.  Its twist E' has size h'r' where h' to the 
> another
> small cofactor and r' is another large prime.
> >
> > Now G be the group of F_p^2 rational points, which is a group of size 
> > hh'rr',
> right?
>
> Nope: Take t=p+1-hr. t is the trace of a matrix with determinant p, say 
> diagonal
> with \alpha and \beta as eigenvalues. |G| = p^2+1-t_2, where
> t_2=\apha^2+\beta^2. Using Viete's formulas, or maybe Newton's, we write
> t^2-2p=t_2. So the order of |G| is p^2+2p+1-(p+1-hr)^2. It's not hh'rr'.
>
> I may have made a typo in the above: check Silverman for the exact details.
>
[DB] Ok, as a sanity check, I just checked the Blake--Seroussi--Smart book. 
The order of G is p^2 + 2p + 1 - t^2, just as say.  But this equals (p+1)-t^2 
= (p+1-t)(p+1+t) = (hr)(h'r'), as I claimed, right?

My original reasoning was as follows. If x corresponds to a point outside 
E(F_p), then there exists y in F_p^2, with (x,y) on E(F_p^2), and the same 
addition law applies to this curve - it has the same equation - so surely 
(x,y) would have an order dividing h'r'.  This led me to conclude that 
E(F_p^2) has subgroups of order r and r', and being abelian, has a subgroup of 
order rr'.  I had thought all this part of the twist security story.

Indeed, when I inquired earlier this year about the risk associated not 
rejecting such x, I remember some people answering that this should be as 
secure as doing ECDH in E(F_p^2).

Or, am I really misunderstanding twist security?