<div dir="ltr">Hello Trevor,<div><br></div><div><br></div><div>Great that you raise these issues.</div><div><br></div><div>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.</div><div><br></div><div>Unfortunately these developments will set back efforts at standardization.</div><div><br></div><div>Clearly to achieve security levels equivalent to AES-128/192/256 will require larger fields and/or larger embedding degrees.</div><div><br></div><div>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. </div><div><br></div><div>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.</div><div><br></div><div>However there is a lot of work to be done now to determine the optimal curve to use for each desired level of security. </div><div><br></div><div><br></div><div>Mike Scott</div><div><br></div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Sep 23, 2016 at 7:15 PM, Trevor Perrin <span dir="ltr"><<a href="mailto:trevp@trevp.net" target="_blank">trevp@trevp.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi all,<br> <br> Last January we discussed elliptic curves for pairing-based crypto<br> ("Curves and code for Identity-based Encryption" [1]).<br> <br> People recommended 256-bit Barreto-Naehrig ("BN") curves [2] for ~128<br> bits security, and code such as:<br> <br> - RELIC from Diego Aranha [3,4]<br> - DCLXVI from Naehrig et al [5]<br> - Golang's version, from Adam Langley [6]<br> - MIRACL from Michael Scott [7]<br> - herumi/ate-pairing from Shigeo and Tadanori [8]<br> <br> Mike Hamburg's comment was insightful [9]:<br> <br> """<br> BN curves only really shine at the ~WF128 level, where a 256-bit curve<br> matches a 256*12-bit extension field discrete log problem (EFDLP). At<br> higher WFs (or if you’re worried about improvements in EFDLP), you<br> need a higher embedding degree so that the EFDLP will be harder, or<br> else a very large base field.<br> """<br> <br> It also seemed like 256-bit BN curves were becoming popular, at least<br> in experimental systems like:<br> - Pond [10], using BBS signatures to prevent message spam<br> - SNARKs [11] as used by Zerocash [12], using pairings for<br> zero-knowledge proofs of correct program execution<br> - Apache Milagro [13,14], which proposes ID-based crypto instead of<br> Certificate Authorities<br> - "Puncturable encryption" [15,16], which proposes Attribute-Based<br> Encryption and Hierarchical IBE for message forward secrecy<br> - (maybe?) Intel SGX, which uses "EPID" group signatures for remote<br> attestation [17,18]<br> <br> Unfortunately, "improvements in EFDLP" (as Mike called it) have<br> seemingly happened, in the last several months.<br> <br> Kim and Barbulescu's "Extended Tower Number Field Sieve" [19] improves<br> the efficiency of calculating "finite field" (i.e. NOT elliptic curve)<br> discrete logs mod p^n, where p is large-ish and n is certain values,<br> like 6 or 12.<br> <br> There was a great writeup by Aurore Guillevic on the ellipticnews blog<br> [20], and in a recent presentation [21]. I'll try to boil it down<br> even more:<br> <br> The attack is relevant to pairing-friendly curves (like BN) that<br> support a "pairing" operation. A pairing maps points on the elliptic<br> curve to values in some "extension field". Security depends on both<br> the EC-DLP for the elliptic curve, and also DLP on the extension<br> field.<br> <br> 256-bit BN curves have a field prime p of 256 bits and an "embedding<br> degree" of 12, so the extension field is mod p^12, where p^12 has 3072<br> bits. The hope was that 256-bit EC-DLP and 3072-bit DLP would both<br> have security ~128 bits, so this would be nicely matched.<br> <br> However, Kim and Barbulescu showed that DLP where the modulus is a<br> 3072-bit (prime^12) is easier than DLP for a 3072-bit prime. How much<br> easier isn't clear, though by a "crude and naive estimation" they<br> suggest increasing the size of relevant curves by a third (Section 6).<br> Mehdi Tibouchi has a similar estimate [22]: "after this attack,<br> 256-bit Barreto-Naehrig curves no longer offer 128 bits of security,<br> but perhaps closer to 96 or so".<br> <br> Which raises questions:<br> <br> * How reliable are the security estimates?<br> <br> * Is this attack likely to be improved?<br> <br> * Can the attacks benefit from precalculation (like Logjam [23]), or<br> does the work have to be repeated for each discrete log?<br> <br> * What curves should new systems be based on?<br> <br> I believe Voltage was using supersingular curves with embedding degree<br> 2 (over a prime field) for Identity-Based Encryption [24]. GCHQ has<br> been promoting the "SAKKE" IBE scheme for various uses [25,26,27], and<br> I believe that uses similar curves [28]. However, IIUC, an embedding<br> degree of 2 means that ~128 bits of security requires a ~1536 bit<br> elliptic curve (to get a 3072 bit extension field). That seems pretty<br> slow, e.g. if a BN pairing is an order-of-magnitude slower than a<br> "regular" elliptic curve scalarmult, this seems like it would be<br> another order of magnitude slower.<br> <br> Are there better options, for ~128 bits security?<br> <br> <br> [1] <a href="https://moderncrypto.org/mail-archive/curves/2015/#402" rel="noreferrer" target="_blank">https://moderncrypto.org/mail-<wbr>archive/curves/2015/#402</a><br> [2] <a href="https://eprint.iacr.org/2005/133" rel="noreferrer" target="_blank">https://eprint.iacr.org/2005/<wbr>133</a><br> [3] <a href="https://github.com/relic-toolkit" rel="noreferrer" target="_blank">https://github.com/relic-<wbr>toolkit</a><br> [4] <a href="https://eprint.iacr.org/2013/722" rel="noreferrer" target="_blank">https://eprint.iacr.org/2013/<wbr>722</a><br> [5] <a href="http://polycephaly.org/projects/dclxvi/" rel="noreferrer" target="_blank">http://polycephaly.org/<wbr>projects/dclxvi/</a><br> [6] <a href="https://godoc.org/golang.org/x/crypto/bn256" rel="noreferrer" target="_blank">https://godoc.org/golang.org/<wbr>x/crypto/bn256</a><br> [7] <a href="https://github.com/miracl/MIRACL/" rel="noreferrer" target="_blank">https://github.com/miracl/<wbr>MIRACL/</a><br> [8] <a href="https://github.com/herumi/ate-pairing" rel="noreferrer" target="_blank">https://github.com/herumi/ate-<wbr>pairing</a><br> [9] <a href="https://moderncrypto.org/mail-archive/curves/2015/000405.html" rel="noreferrer" target="_blank">https://moderncrypto.org/mail-<wbr>archive/curves/2015/000405.<wbr>html</a><br> [10] <a href="https://github.com/agl/pond" rel="noreferrer" target="_blank">https://github.com/agl/pond</a><br> [11] <a href="https://eprint.iacr.org/2013/507" rel="noreferrer" target="_blank">https://eprint.iacr.org/2013/<wbr>507</a><br> [12] <a href="http://zerocash-project.org/media/pdf/zerocash-oakland2014.pdf" rel="noreferrer" target="_blank">http://zerocash-project.org/<wbr>media/pdf/zerocash-<wbr>oakland2014.pdf</a><br> [13] <a href="https://milagro.apache.org/" rel="noreferrer" target="_blank">https://milagro.apache.org/</a><br> [14] <a href="http://docs.milagro.io/en/amcl/milagro-crypto-library-white-paper.html" rel="noreferrer" target="_blank">http://docs.milagro.io/en/<wbr>amcl/milagro-crypto-library-<wbr>white-paper.html</a><br> [15] <a href="https://github.com/imichaelmiers/libforwardsec/" rel="noreferrer" target="_blank">https://github.com/<wbr>imichaelmiers/libforwardsec/</a><br> [16] <a href="https://www.computer.org/csdl/proceedings/sp/2015/6949/00/6949a305.pdf" rel="noreferrer" target="_blank">https://www.computer.org/csdl/<wbr>proceedings/sp/2015/6949/00/<wbr>6949a305.pdf</a><br> [17] <a href="https://eprint.iacr.org/2009/095" rel="noreferrer" target="_blank">https://eprint.iacr.org/2009/<wbr>095</a><br> [18] <a href="https://www.blackhat.com/docs/us-16/materials/us-16-Aumasson-SGX-Secure-Enclaves-In-Practice-Security-And-Crypto-Review-wp.pdf" rel="noreferrer" target="_blank">https://www.blackhat.com/docs/<wbr>us-16/materials/us-16-<wbr>Aumasson-SGX-Secure-Enclaves-<wbr>In-Practice-Security-And-<wbr>Crypto-Review-wp.pdf</a><br> [19] <a href="https://eprint.iacr.org/2015/1027" rel="noreferrer" target="_blank">https://eprint.iacr.org/2015/<wbr>1027</a><br> [20] <a href="https://ellipticnews.wordpress.com/2016/05/02/kim-barbulescu-variant-of-the-number-field-sieve-to-compute-discrete-logarithms-in-finite-fields/" rel="noreferrer" target="_blank">https://ellipticnews.<wbr>wordpress.com/2016/05/02/kim-<wbr>barbulescu-variant-of-the-<wbr>number-field-sieve-to-compute-<wbr>discrete-logarithms-in-finite-<wbr>fields/</a><br> [21] <a href="https://www.lorentzcenter.nl/lc/web/2016/834/presentations/Guillevic" rel="noreferrer" target="_blank">https://www.lorentzcenter.nl/<wbr>lc/web/2016/834/presentations/<wbr>Guillevic</a><br> [22] <a href="https://ellipticnews.wordpress.com/2016/09/02/crypto-and-ches-2016-santa-barbara-ca-usa/" rel="noreferrer" target="_blank">https://ellipticnews.<wbr>wordpress.com/2016/09/02/<wbr>crypto-and-ches-2016-santa-<wbr>barbara-ca-usa/</a><br> [23] <a href="https://weakdh.org/" rel="noreferrer" target="_blank">https://weakdh.org/</a><br> [24] <a href="https://tools.ietf.org/html/rfc5091" rel="noreferrer" target="_blank">https://tools.ietf.org/html/<wbr>rfc5091</a><br> [25] <a href="https://www.benthamsgaze.org/wp-content/uploads/2016/01/SA3LI10_099.pdf" rel="noreferrer" target="_blank">https://www.benthamsgaze.org/<wbr>wp-content/uploads/2016/01/<wbr>SA3LI10_099.pdf</a><br> [26] <a href="https://tools.ietf.org/html/draft-barnes-mikey-sakke-mcptt-00" rel="noreferrer" target="_blank">https://tools.ietf.org/html/<wbr>draft-barnes-mikey-sakke-<wbr>mcptt-00</a><br> [27] <a href="http://www.securechorus.com/" rel="noreferrer" target="_blank">http://www.securechorus.com/</a><br> [28] <a href="https://tools.ietf.org/html/rfc6508" rel="noreferrer" target="_blank">https://tools.ietf.org/html/<wbr>rfc6508</a><br> <br> <br> Trevor<br> ______________________________<wbr>_________________<br> Curves mailing list<br> <a href="mailto:Curves@moderncrypto.org">Curves@moderncrypto.org</a><br> <a href="https://moderncrypto.org/mailman/listinfo/curves" rel="noreferrer" target="_blank">https://moderncrypto.org/<wbr>mailman/listinfo/curves</a><br> </blockquote></div><br></div>