2016-09-23 18:15:57 UTC
Last January we discussed elliptic curves for pairing-based crypto
("Curves and code for Identity-based Encryption" ).
People recommended 256-bit Barreto-Naehrig ("BN") curves  for ~128
bits security, and code such as:
- RELIC from Diego Aranha [3,4]
- DCLXVI from Naehrig et al 
- Golang's version, from Adam Langley 
- MIRACL from Michael Scott 
- herumi/ate-pairing from Shigeo and Tadanori 
Mike Hamburg's comment was insightful :
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 , using BBS signatures to prevent message spam
- SNARKs  as used by Zerocash , using pairings for
zero-knowledge proofs of correct program execution
- Apache Milagro [13,14], which proposes ID-based crypto instead of
- "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
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"  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
, and in a recent presentation . I'll try to boil it down
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
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 : "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 ), 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 . GCHQ has
been promoting the "SAKKE" IBE scheme for various uses [25,26,27], and
I believe that uses similar curves . 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?