[curves] Curves for pairings

[Trevor Perrin]

Hi all,

Last January we discussed elliptic curves for pairing-based crypto
("Curves and code for Identity-based Encryption" [1]).

People recommended 256-bit Barreto-Naehrig ("BN") curves [2] for ~128
bits security, and code such as:

 - RELIC from Diego Aranha [3,4]
 - DCLXVI from Naehrig et al [5]
 - Golang's version, from Adam Langley [6]
 - MIRACL from Michael Scott [7]
 - herumi/ate-pairing from Shigeo and Tadanori [8]

Mike Hamburg's comment was insightful [9]:

"""
BN curves only really shine at the ~WF128 level, where a 256-bit curve
matches a 256*12-bit extension field discrete log problem (EFDLP).  At
higher WFs (or if you’re worried about improvements in EFDLP), you
need a higher embedding degree so that the EFDLP will be harder, or
else a very large base field.
"""

It also seemed like 256-bit BN curves were becoming popular, at least
in experimental systems like:
 - Pond [10], using BBS signatures to prevent message spam
 - SNARKs [11] as used by Zerocash [12], using pairings for
zero-knowledge proofs of correct program execution
 - Apache Milagro [13,14], which proposes ID-based crypto instead of
Certificate Authorities
 - "Puncturable encryption" [15,16], which proposes Attribute-Based
Encryption and Hierarchical IBE for message forward secrecy
 - (maybe?) Intel SGX, which uses "EPID" group signatures for remote
attestation [17,18]

Unfortunately, "improvements in EFDLP" (as Mike called it) have
seemingly happened, in the last several months.

Kim and Barbulescu's "Extended Tower Number Field Sieve" [19] improves
the efficiency of calculating "finite field" (i.e. NOT elliptic curve)
discrete logs mod p^n, where p is large-ish and n is certain values,
like 6 or 12.

There was a great writeup by Aurore Guillevic on the ellipticnews blog
[20], and in a recent presentation [21].  I'll try to boil it down
even more:

The attack is relevant to pairing-friendly curves (like BN) that
support a "pairing" operation.  A pairing maps points on the elliptic
curve to values in some "extension field".  Security depends on both
the EC-DLP for the elliptic curve, and also DLP on the extension
field.

256-bit BN curves have a field prime p of 256 bits and an "embedding
degree" of 12, so the extension field is mod p^12, where p^12 has 3072
bits.  The hope was that 256-bit EC-DLP and 3072-bit DLP would both
have security ~128 bits, so this would be nicely matched.

However, Kim and Barbulescu showed that DLP where the modulus is a
3072-bit (prime^12) is easier than DLP for a 3072-bit prime.  How much
easier isn't clear, though by a "crude and naive estimation" they
suggest increasing the size of relevant curves by a third (Section 6).
Mehdi Tibouchi has a similar estimate [22]:  "after this attack,
256-bit Barreto-Naehrig curves no longer offer 128 bits of security,
but perhaps closer to 96 or so".

Which raises questions:

 * How reliable are the security estimates?

 * Is this attack likely to be improved?

 * Can the attacks benefit from precalculation (like Logjam [23]), or
does the work have to be repeated for each discrete log?

 * What curves should new systems be based on?

I believe Voltage was using supersingular curves with embedding degree
2 (over a prime field) for Identity-Based Encryption [24].  GCHQ has
been promoting the "SAKKE" IBE scheme for various uses [25,26,27], and
I believe that uses similar curves [28].  However, IIUC, an embedding
degree of 2 means that ~128 bits of security requires a ~1536 bit
elliptic curve (to get a 3072 bit extension field).  That seems pretty
slow, e.g. if a BN pairing is an order-of-magnitude slower than a
"regular" elliptic curve scalarmult, this seems like it would be
another order of magnitude slower.

Are there better options, for ~128 bits security?


[1] https://moderncrypto.org/mail-archive/curves/2015/#402
[2] https://eprint.iacr.org/2005/133
[3] https://github.com/relic-toolkit
[4] https://eprint.iacr.org/2013/722
[5] http://polycephaly.org/projects/dclxvi/
[6] https://godoc.org/golang.org/x/crypto/bn256
[7] https://github.com/miracl/MIRACL/
[8] https://github.com/herumi/ate-pairing
[9] https://moderncrypto.org/mail-archive/curves/2015/000405.html
[10] https://github.com/agl/pond
[11] https://eprint.iacr.org/2013/507
[12] http://zerocash-project.org/media/pdf/zerocash-oakland2014.pdf
[13] https://milagro.apache.org/
[14] http://docs.milagro.io/en/amcl/milagro-crypto-library-white-paper.html
[15] https://github.com/imichaelmiers/libforwardsec/
[16] https://www.computer.org/csdl/proceedings/sp/2015/6949/00/6949a305.pdf
[17] https://eprint.iacr.org/2009/095
[18] https://www.blackhat.com/docs/us-16/materials/us-16-Aumasson-SGX-Secure-Enclaves-In-Practice-Security-And-Crypto-Review-wp.pdf
[19] https://eprint.iacr.org/2015/1027
[20] https://ellipticnews.wordpress.com/2016/05/02/kim-barbulescu-variant-of-the-number-field-sieve-to-compute-discrete-logarithms-in-finite-fields/
[21] https://www.lorentzcenter.nl/lc/web/2016/834/presentations/Guillevic
[22] https://ellipticnews.wordpress.com/2016/09/02/crypto-and-ches-2016-santa-barbara-ca-usa/
[23] https://weakdh.org/
[24] https://tools.ietf.org/html/rfc5091
[25] https://www.benthamsgaze.org/wp-content/uploads/2016/01/SA3LI10_099.pdf
[26] https://tools.ietf.org/html/draft-barnes-mikey-sakke-mcptt-00
[27] http://www.securechorus.com/
[28] https://tools.ietf.org/html/rfc6508


Trevor