Subject: [Cfrg] On curves

From: Watson Ladd <[email-masked]>
Date: Wed, 2 Jul 2014 19:37:34 -0700

Dear all,
After thinking about it for a bit, I've come up with the following
summary of my current position.

For compressed Edwards points, having p=3 (mod 4) is slightly easier
to explain how to deal with then p =5 (mod 8). We want to have the
same prime

There is no point to adding additional Weierstrass curves: additional
performance alone isn't that compelling unless implementors want to
implement a bunch of curves. Doing a good implementation is a bunch of
work, and in particular while a saturated word arithmetic is easy,
it's not worth doing unsaturated arithmetic unnecessarily.

Likewise the difference between 2^256 and 2^255 is minor in security,
but has a performance hit. so I would try to avoid going over word
boundaries.

As a result I suggest a Montgomery curve and isogenous twisted Edwards
curve with primes of the form p=2^(64*b-1)-c, c minimal so p is 3 (mod
4). I believe these have been computed by Longa et all.

However, at the 128 bit level, I see no technical arguments against
Curve25519. It's really a WG decision as how to do it.

This leaves the question of point representation: I would use Edwards
form with point compression: the Montgomery form has advantages in
variable-base multiplication, but it appears that summing the time of
one variable-base multiplication with one fixed-base multiplication
comes out lower for Edwards form. Again, for everything but signatures
the difference is probably minor.

Sincerely,
Watson Ladd

---

From: Michael Hamburg <[email-masked]>
Date: Wed, 2 Jul 2014 23:00:06 -0400

Thanks for your perspective, Watson!

But, how should we proceed?  We have, now, at least four pieces of code which aim for eventual production-grade Edwards curve crypto.  None of them entirely follows your suggestions:

* Ed25519, which uses Edwards coordinates, p=5 mod 8, and an extra bit sign encoding;

* Snowshoe, with endomorphisms over GF((2^127-1)^2), and I think no compression;

* The Microsoft curves, which have code released for p = 2^(64b)-minimal, p=3 mod 4, and no point compression;

* Ed448-Goldilocks, which uses a Solinas prime and a 1/sqrt(x) point representation.

Are you requesting that the Microsoft folks release implementations of some of their other curves?

Cheers,
— Mike

On Jul 2, 2014, at 10:37 PM, Watson Ladd <[email-masked]> wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Watson Ladd <[email-masked]>
Date: Wed, 2 Jul 2014 20:35:00 -0700

> Are you requesting that the Microsoft folks release implementations of some of their other curves?

Yes, and I think we should change some choices. Adding point
compression with a separate sign bit is not that tricky, but I can't
remember when the patent expires. (I'm also not volunteering: my
timeframe for completion doesn't line up). Alternatively we decide
which of these is the closest to some reasonable ideal/doesn't offend
too many people.

Sincerely,
Watson Ladd

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 2 Jul 2014 20:48:44 -0700

On Wed, Jul 2, 2014 at 7:37 PM, Watson Ladd <[email-masked]> wrote:

> implement a bunch of curves

Yes! Additional curves for the sake of additional curves is not helpful,
and the new Weierstrass curves are not particularly compelling in terms of
security, popularity, robustness, or general health of the surrounding
ecosystem.

I'll leave you with this quote:

"If you don’t actively fight for simplicity in software, complexity will
win, and it will suck."

-- 
Tony Arcieri

---

From: Alyssa Rowan <[email-masked]>
Date: Thu, 03 Jul 2014 07:31:51 +0100

On 03/07/2014 04:35, Watson Ladd wrote:

> compression with a separate sign bit is not that tricky, but I 
> can't remember when the patent expires.

US6141420 (Certicom: Vanstone-Mullin-Agnew) has a priority date of
1994-07-29, so (to my understanding, and I believe djb's?) expires
2014-07-29 - a little under 4 weeks from now!

Fortuitous timing, and I'm definitely not a patent expert, so I don't
feel comfortable stating that for sure, and I don't know if there are
any others that would be relevant to Edwards curve point compression.

Employees of Certicom on this list: could you please check - is that
correct? Are you aware of any other patents covering point compression
with one sign bit? [I'm aware you've been slow on IPR issues recently
due to internal issues, but you -do- have a duty to disclose anything
that may pertain in a reasonable timeframe.]

- -- 
/akr