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

From: Dan Brown <[email-masked]>
Date: Thu, 4 Dec 2014 22:17:04 +0000

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.

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Thu, 04 Dec 2014 23:34:35 +0100

Hi,

On 04/12/2014 23:17, Dan Brown wrote:
> 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.
> 
I'm way too tired to check if the above is correct, but it seems to me that
complete laws for general curves are known, see eg 29.1.2.a of the Handbook of
Elliptic and Hyperelliptic Curve Cryptography (Cohen, Frey et al.).

I'm not sure it makes such a lot of sense to classify that as an efficiency
rather than security issue: in my opinion (which seems to be shared by many
people), conflicts between efficiency and security are to be avoided as much as
possible, since in practice, they will very often result in security issues.

Manuel.

---

From: Watson Ladd <[email-masked]>
Date: Thu, 4 Dec 2014 20:47:24 -0800

> Elliptic and Hyperelliptic Curve Cryptography (Cohen, Frey et al.).

That formula is accompanied by a discussion pointing out there is an
exceptional case, and so one has to switch between two different
formulas by reversing the order of coordinates under some conditions.
It's also unclear that infinity as an output or as an input is handled
correctly. (In fact, I think they aren't: if we add P to -P, the
denominator does not vanish, unless I'm missing something) Those
formulas would be "strongly unified" in the language of the EFD if I
understand correctly, but not "complete".

Sincerely,
Watson Ladd

---

From: Samuel Neves <[email-masked]>
Date: Sat, 06 Dec 2014 21:26:54 +0000

> 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 additi…

If you read Lenstra-Bosma, you will see that what you call (G:H:I) is already complete (in the field) for curves with
cofactor 1: the exceptional points for the second formula are exactly the points for which P1 - P2 has Y = 0, which does
not happen in cofactor 1. More generally, Arene,  Kohel, and Ritzenthaler (https://arxiv.org/abs/1102.2349, Theorem 4.3)
have shown that any elliptic curve, regardless of cofactor, has a complete addition formula in the field.

---

From: Dan Brown <[email-masked]>
Date: Mon, 8 Dec 2014 18:46:13 +0000

> -----Original Message-----
> From: Samuel Neves
> Sent: Saturday, December 06, 2014 4:27 PM
> 
> 
> If you read Lenstra-Bosma, you will see that what you call (G:H:I) is
already
> complete (in the field) for curves with cofactor 1: the exceptional points
for the
> second formula are exactly the points for which P1 - P2 has Y = 0, which
does
> not happen in cofactor 1. More generally, Arene,  Kohel, and Ritzenthaler
> (https://arxiv.org/abs/1102.2349, Theorem 4.3) have shown that any
elliptic
> curve, regardless of cofactor, has a complete addition formula in the
field.
[DB] Thanks, very helpful!

So ... the table from http://safecurves.cr.yp.to/complete.html - which
"reports support for the complete elliptic scalar multiplication" - has an
entry of "False" in the row P256 because the complete formulas for P256 fall
under the proviso that they "are considerably slower and more complicated
than standard incomplete ... formulas".   Well, I missed that proviso, and
in particular, missed the fact that k-complete formula are known for all
curves.

Regarding that proviso, I wonder how much the second Bosma-Lenstra formula
(the one I called (G:H:I), which is the one that corresponds to the line
(0:1:0) in the Bosma-Lenstra paper) would be slower than the standard
incomplete formula.  That is, has anybody tried to optimize it?  (Naively,
with a small a_4, I get a cost of 51M, but I expect much better is
possible.)  Also, there seems to be many k-complete formula per curve, and
perhaps some are faster than others, is this studied?

Also, does the security gain of k-completeness warrant the efficiency loss,
if one, say had to use a cofactor 1 curve, e.g. a grandfathered
P256/Brainpool curve?  (I'm guessing that, in most cases, a Brier-Joye
(Montgomery) x-only ladder would be secure enough, and probably faster.)

Best regards,

Dan

---

From: Samuel Neves <[email-masked]>
Date: Mon, 08 Dec 2014 21:11:26 +0000

> perhaps some are faster than others, is this studied?

Both Arene-Kohel-Ritzenhaler (https://arxiv.org/abs/1102.2349, Remark 4.4) and Bos-Costello-Longa-Naehrig
(https://eprint.iacr.org/2014/130, pg 37) present simplified formulas, both beating 51M. I don't know of other attempts
to optimize complete Weierstrass formulas.