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

From: Dan Brown <[email-masked]>
Date: Mon, 2 Nov 2015 15:49:54 +0000

http://ia.cr/2015/1060

seems to finally have more efficient answers to the old questions above and
below.

> -----Original Message-----
> From: Samuel Neves [mailto:[email-masked]]
> Sent: Monday, December 08, 2014 4:11 PM
> To: Dan Brown; [email-masked]'
> Subject: Re: [Cfrg] Complete additon for cofactor 1 short Weierstrass
curve?
> 
> On 08-12-2014 18:46, Dan Brown wrote:
> > 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?
> 
> 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.

---

From: Watson Ladd <[email-masked]>
Date: Mon, 2 Nov 2015 11:20:44 -0500

It's completely irrelevant in practice. Multiplying points by 4 or 8
before hashing and after subtracting for equality checks produces a
prime order group without the efficiency loss inherent to these
formulas. Furthermore, applications we have today only rely on ECDH
and signatures, both of which are specified with arbitrary cofactor in
NIST standards, for instance.

On Mon, Nov 2, 2015 at 10:49 AM, Dan Brown <[email-masked]> wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Nathaniel McCallum <[email-masked]>
Date: Mon, 02 Nov 2015 11:39:38 -0500

On Mon, 2015-11-02 at 11:20 -0500, Watson Ladd wrote:
> and signatures

... and SPAKE. Chromium already implements it. MIT krb5 has an
implementation in a branch.

---

From: Dan Brown <[email-masked]>
Date: Wed, 4 Nov 2015 17:41:09 +0000

> From: Watson Ladd
> Sent: Monday, November 02, 2015 11:21 AM
> 
> It's completely irrelevant in practice. 
[DB] Seems a tad overstated. How about: too little, too late.

> Multiplying points by 4 or 8 before
> hashing and after subtracting for equality checks produces a prime order
group
> without the efficiency loss inherent to these formulas. 

Cofactor-1 curves obviate the need for cofactor-multiplication (e.g.
multiplying by 4 or 8). In that regard, they improve implementation-fault
tolerance: one less thing for an implementer to get wrong - similar in
principle to using twist-security or pseudo-randomized signatures.  The
efficiency loss you mention is now quite a tolerable loss, due to this new
paper.  Given the relatively tolerable efficiency, the deciding question
should be about security.  

Does cofactor-multiplication plus Montgomery ladder provide better
(implementation-fault) security than cofactor-1 complete addition laws?

Maybe. Under the theory that implementers mostly err by over-optimizing for
efficiency, heedlessly skimping on security checks, then cofactor-4 plus
Montgomery seems less vulnerable to such errors, because ladders look to be
the fastest laws for cofactor-4 curves, whereas complete laws for cofactor-1
curves are still not the fastest laws.  Such a security argument is more
persuasive (to me) than the efficiency argument. That said, I'm not
completely sure of that argument either.

Cofactor-1 curves also have the property that the curve representation
itself can easily exclude small-subgroup points, by placing the weak points
on the line at infinity.  That property has only miniscule security benefit,
as far as I know.

---

From: Watson Ladd <[email-masked]>
Date: Wed, 4 Nov 2015 14:08:51 -0500

> should be about security.

An implementor who removes a multiplication by 4 where it matters will
get the wrong result and the keys they derive will fail to agree with
the other end. An implementor who uses incomplete formulas is not
guaranteed to notice.

---

From: Michael Hamburg <[email-masked]>
Date: Wed, 4 Nov 2015 18:03:25 -0800

> On Nov 4, 2015, at 11:08 AM, Watson Ladd <[email-masked]> wrote:
> 

[MH]: I agree with [DB] that this paper is useful, but unlikely to be widely deployed because of its speed penalty vs the unsafe method.  But for general-purpose libraries and niche protocols that really can’t guarantee safety with non-unified formulas, this is an important step forward.  It may not quite level the playing with Edwards, but at least it avoids a potentially show-stopping problem with prime-order curves.

Cheers,
— Mike