Subject: [Cfrg] Requirements, part II

From: Watson Ladd <[email-masked]>
Date: Tue, 28 Oct 2014 08:24:16 -0700

Dear all,
Benchmarks are only going to help decide which curves offer high
security at reasonable price, and leave plenty of other things open.
With that in mind I'm hoping to summarize the various decisions that
need to get made.

The first decision: what point format? Don't say "we can leave it up
to WGs" because before you know it there will be six different ones,
all of which implementers have to deal with.

Weierstrass form is backwards compatible. This is both a blessing and
a curse. It's a blessing because no one has to write new code. It's a
curse because no one will, unless they need the performance gains, so
the security gains won't happen as quickly. It does mean that it's
easier to adopt the new curves. (How bad is the cofactor issue?
Unclear)

Representing points on a curve in a coordinate system with complete
addition law for all possible primes requires Edwards form. Twisted
Edwards with a=-1 is not necessary complete, and sadly 2^521-1 is a
prime where it isn't.

Montgomery form is extremely simple to add to an implementation, and
in ECDH only scenarios very nice. Yes, there are protocols that only
need encryption, and so can do this.

Compressed codepoints mitigate a security issue, at the cost of a 10%
or so decompression PITA on verification in signatures and ECDH.

The endianness issue needs to get settled one way or the other. I wish
one side had won a complete victory, but sadly this is not the case.

The second decision: what to do about signatures? ECDSA seems like it
can handle cofactors, but the official standard is not free, so I
couldn't verify this. It does require Weierstrass form, and does have
a painful inversion both for signers and verifiers.

The Schnorr signature scheme is much faster, has batchable variants
(less of a win then you might think), and is finally unpatented. The
absence of an inversion makes implementing simple and increases
performance.

These decisions need to get made no matter what curves we choose.

Sincerely,
Watson Ladd

---

From: Andy Lutomirski <[email-masked]>
Date: Tue, 28 Oct 2014 09:37:31 -0700

> absence of an inversion makes implementing simple and increases

To the extent that performance matters for certain parts of certain
protocols, CFRG could suggest that, where practical, new ECDH-using
protocols that need authentication should avoid using signatures at
all.

For example, I see no reason that a TLS server, even one offering
Channel ID or some similar mechanism, should need to sign anything or
verify a signature for each new connection.  There are any number of
very simple protocols that can prove knowledge of an EC private key
with a single scalar multiplication.

--Andy