Subject: Re: [Cfrg] Call for adoption: draft-yonezawa-pairing-friendly-curves

From: Chloe Martindale <[email-masked]>
Date: Sat, 7 Sep 2019 19:17:13 +0200

Dear CFRG,

I'm joining this list rather late, sorry for that. I would also like to
suggest a couple of changes and additions to the draft.

1. Currently the draft focusses on the security of currently-in-use
implementations and the smallest alterations possible to achieve 128-bit
(resp. 256-bit) security. On this I have one small comment: The security
levels of BN462 and BLS12-381 have been refined since [BD18], they are now
understood to be 134-bit and 126-bit secure respectively, see [GMT19].

2. I think it would be beneficial to name the safest known choice for
128-bit security. I would argue that BN462 is not really a 'conservative
choice' since further improvements on the NFS attacks are still quite
likely and could definitely weaken this to below 128 bits of security. I
would instead recommend the k=8 Cocks-Pinch curve of [GMT19] as a
conservative choice, since the NFS attacks do not apply to this curve. It
is also considerably more efficient than BN462 (but of course has the
disadvantage that it is not already implemented in industry). An
alternative (I guess slightly slower but still practical?!) recommendation
could be the Cocks-Pinch curve SW6 mentioned by Kobi as something already
in use in the wild?

3. I think it would be good to give some indication of performance
differences between the recommendations, for example by referring to the
tables of [GMT19]. If you want to give the most efficient choice to date
(theoretically), there are the Family 17 curves of [FM19]. Of course if you
allow slightly less than 128 bits of security you can also take BLS12-381,
or an equivalent choice in the family of [FM19], which one would expect to
be faster than BLS12-381 by a factor of about 15%. Having not yet had any
industry-level implementations, it might be too soon to really recommend
these curves, but it is probably good to mention that the recommendations
in this document (so BLS, BN, and Cocks-Pinch) are definitely not the most
efficient choices out there.

4. Regarding 192-bit secure curves. There are two recommendations in
[FM19], so perhaps these can go in the currently empty section of the draft.

I would in principle be happy to work on the draft myself in order to
incorporate these things.

[GMT19] https://eprint.iacr.org/2019/431.pdf
[FM19]  https://eprint.iacr.org/2019/555.pdf

Chloe Martindale
Eindhoven University of Technology

---

From: Jeff Burdges <[email-masked]>
Date: Sat, 7 Sep 2019 22:23:13 +0200

Amen!

Right now, there are two common usages for pairing friendly curves that
both come with an upgrade path that makes a less conservative choice
sound reasonable:

1) Aggregatable signatures are being used consensus protocols, but these
networks are increasingly being designed to support in network upgrades,
and consensus protocol keys should be relatively short lived.  And these
upgrade may not touch the users.

2) Zero-knowledge proof systems like zcash are willing to pay the cost
of upgrading the network, including the users, both because they are
quite sensitive to performance, and also because their complexity means
that improvements or bug fixed requires upgrading the crypto.

You cannot expect this same emphasis on an upgrade path from most users.

In particular, one should expect increased interest in using BLS-like
signature where threshold/multi signatures suffice, in part due to the
parallel signing attacks on almost all 2-RTT threshold/multi signatures
without pairings:  https://eprint.iacr.org/2018/417.pdf

Jeff