[Cfrg] Complete additon for cofactor 1 short Weierstrass curve?

[Dan Brown <[e-mail]>]

Hi CFRG list,



I've interpreted some statements on the CFRG list, and some external web sites, as suggesting the cofactor 1 short Weierstrass curves like P256 do not have (known?) "complete" addition laws (and then, that this would be a potential security problem?).  Possibly, I'm misunderstanding these statements because I think that there is a complete addition law for such curves, described below (if this existence is known, then just skip to the end of this message).



First, Figure 1.2 from http://eprint.iacr.org/2009/580.pdf adapted from Bosma and Lenstra, gives two formulas, which I'll abbreviate to (D:E:F) and (G:H:I), for the sum of two points (in terms of their standard projective coordinates).  These two laws form a complete set, which means, I think, that, for any two input points, (a) at least one of them does not evaluate to (0:0:0), and (b) any evaluation, other than (0:0:0), is the correct value, i.e. a projective representation of the sum of the points.  (Actually, I'm not totally sure about (b): can one of these laws evaluate an incorrect point different from (0:0:0)?  The elementary argument below _assumes_ that this worse kind of failure cannot happen.)



Second, let t be an element of degree 2 over F_p with t^2 = u, for u a non-quadratic residue.  Then the law (D+tG : E+tH : F+tI) is another valid addition law, except possibly where it takes value (0:0:0), because it on the line between (D:E:F) and (G:H:I), and thus represents the same point.  When adding two points with F_p coordinates, this never results (0:0:0), because then both (D:E:F) and (G:H:I) would evaluate to (0:0:0).



Third, if the curve has "cofactor 1", then there is no F_p-rational point of order 2, which means that E+tH never evaluates to zero when the output point has coordinates in F_p.  (And the point at infinity is (0:1:0), so it too has a nonzero value for E+tH.)  So, we can multiply by the previous law by the conjugate E-tH of the Y coordinate, and then drop any remaining t terms from X and Z expressions, because their coefficients must vanish on F_p rational points once the Y coordinate is scaled to be in F_p, to get the law (DE - uGH : E^2 - uH^2 : FE - uHI). This should be complete in the sense that, for F_p rational input points, it never results in (0:0:0), because it is just a nonzero scaling of the previous law, (or because E^2 - uH^2 is the norm of E+tH, which is nonzero on the points of interests).



Well, I haven't really studied these kinds of things before: I more often think of elliptic curves as generic groups, so I could easily be mistaken (e.g. maybe the incorrect outputs really can differ from (0:0:0), or something really wrong in the logic above).  So, I ask the experts here on this list: Is this addition law correct?  Is it complete in the same sense used for Edwards curves?



If this is all correct, then I would suggest that cofactor 1 short Weierstrass do not have a security problem compared to Edwards curves (e.g. cofactor 4), in the sense of lacking a complete addition law, but rather, just an efficiency problem, in the sense of not having any (known) efficient complete law.



Best regards,



Daniel Brown

Research In Motion Limited













---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.