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

[Dan Brown <[e-mail]>]

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