[curves] Curves for pairings

Sat Sep 24 08:00:53 PDT 2016

Hello Trevor,

Great that you raise these issues.

In my opinion the new security estimates are reliable. There was always a
suspicion (I recall discussing it over a decade ago) that the DL problem in
these fields might/must be easier due to the special form of the modulus
used in pairing-friendly constructions like BN curves. However for what its
worth my gut tells me that further improvements may be difficult.

Unfortunately these developments will set back efforts at standardization.

Clearly to achieve security levels equivalent to AES-128/192/256 will
require larger fields and/or larger embedding degrees.

I would tentatively suggest that BN curves (which appeared to be such a
perfect fit for AES-128 security), may no longer be so useful. Which is a
bit tragic, as they were so nice! And we will have to live with curves with
a \rho value greater than 1.

I suspect that BLS curves with k=12 must now be a better fit (but maybe not
the best) for AES-128. Here we are experimenting with a 455-bit BLS curve,
derived from the parameter x=0x10000020000080000800. In some experiments
our code is 2.5 times slower to calculate a pairing on this curve compared
with a 256-bit BN curve.

However there is a lot of work to be done now to determine the optimal
curve to use for each desired level of security.

Mike Scott

On Fri, Sep 23, 2016 at 7:15 PM, Trevor Perrin <trevp at trevp.net> wrote:

> 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
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20160924/9daa34d4/attachment.html>