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

So, I’m not a lawyer, and I haven’t read the full patent, but the applicability of the quoted claims seems like a stretch to me.

In the case of a full elliptic curve implementation, the group G that’s actually implemented is only the points on the elliptic curve, having order hr in your notation.  The formulas will usually be completely wrong for the twist, and they of course won’t handle general points in F_p^2.  So it doesn’t make sense to say that the author implemented a subgroup S of E(F_p^2) with order rr’, or hh’rr’, or anything like that, or that it was “selected” or “utilised" for key agreement.  In this case, twist security isn’t very important anyway, because if you don’t do a curve membership check (possibly as part of decompression) you’ll get the wrong answer and will be exposed to attack.

In the case of an x-only implementation like X25519, where twist security matters, an algorithm like the Montgomery ladder does not implement a group at all.  Instead it implements only a powering/scalarmul map on the Kummer surface of the curve union its twist, and again not anything like a large subgroup of E(F_p^2).

— Mike

> On Nov 26, 2014, at 11:12 AM, Dan Brown <dbrown@certicom.com> wrote:
> 
> 
>> -----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?
> 
> 
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg