[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

[Michael Scott]

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

Post by 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
- 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]
"""
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
- 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
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".
* 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
https://moderncrypto.org/mailman/listinfo/curves

[Zooko Wilcox-OHearn]

Thank you for doing this research and posting, trevp!

I'm glad to hear this opinion from Mike Scott that these attacks on BN
curves are unlikely to get a lot better, because in the Zcash project,
which is the new version of the Zerocash protocol ¹, we decided that
we would just stick with BN128 for now rather than try to hastily find
a new curve. Our deliberations about that are visible here: ².

What it boils down to is:

a) We believed (uncertainly) that BN128 still has at least 96 bits of
security, taking this attack into account. I'm glad of this email
thread to help bring to our attention any reasons to think otherwise!

and

b) Pairing performance is critical for us. A curve like Michael Scott
suggested that took 2.5 times as long for a pairing operation would
almost certainly blow our performance budget and we'd have to do some
serious re-engineering to get it back.

Sincerely,

Zooko

¹ https://z.cash/blog/fixing-zcash-vulns.html

² https://github.com/zcash/zcash/issues/714# understand the concrete
security level of the BN_128 curve in libsnark

Post by Michael Scott
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

Post by 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
- 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]
"""
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
- 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
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".
* 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
https://moderncrypto.org/mailman/listinfo/curves

_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves

[Zooko Wilcox-OHearn]

following-up to my own post

On Sun, Sep 25, 2016 at 11:58 PM, Zooko Wilcox-OHearn

Post by Zooko Wilcox-OHearn
b) Pairing performance is critical for us. A curve like Michael Scott
suggested that took 2.5 times as long for a pairing operation would
almost certainly blow our performance budget and we'd have to do some
serious re-engineering to get it back.

I was totally wrong about this. Our performance bottleneck is in a
path (zk-SNARK proving) that doesn't require pairing operations, so
using a curve which was 2.5 times slower at pairing operations would
not worsen our performance issues. However, if it was also 2.5 slower
for curve operations, then it would.

Proving time:

https://speed.z.cash/timeline/?exe=1&base=1%2B9&ben=time+createjoinsplit&env=1&revs=1000&equid=off&quarts=on&extr=on

Verifying time:

https://speed.z.cash/timeline/?exe=1&base=1%2B9&ben=time+verifyjoinsplit&env=1&revs=1000&equid=off&quarts=on&extr=on

I guess it might also be an issue if our verifier took a lot longer,
but it's currently unclear how serious of a problem that would be.

Also, Zcash engineer Sean Bowe said this to me, and I completely don't
understand what he is talking about so I'm just writing it in here
verbatim:

"hopefully if work is done on BLS curves, they will select a curve
that works well for snarks. i.e. with group order p such that p-1 is a
multiple of 2^28 or another large power of 2"

Sincerely,

Zooko

[Jeff Burdges]

Post by Zooko Wilcox-OHearn
I was totally wrong about this. Our performance bottleneck is in a
path (zk-SNARK proving) that doesn't require pairing operations, so
using a curve which was 2.5 times slower at pairing operations would
not worsen our performance issues. However, if it was also 2.5 slower
for curve operations, then it would.

It's still slower for scalar multiplication due to being a larger curve,
no?

In any case, you said there are no risks to the anonymity here, so an
alternative to changing curves might be to prevent attacks from being
profitable by capping the maximum value in a transaction or account,
right? In the short term, this should not require dong anything.

Jeff

[Brendan McMillion]

Hey Mike,

This morning, I forked Golang's implementation of bn256 and fit it with a
448-bit BN [1] curve based on the parameter

u = 1910986621940954212840033034977453

which, according to ellipticnews, should be closer to the 128-bit security
level. Interestingly, it's also very close to 2.5 times slower than the
same implementation for a 256-bit curve for all major operations. For
scalar mult in G1, 2 milliseconds to 5ms. For scalar mult in G2, 5ms to
13ms. For a pairing, 15ms to 35ms. All of these numbers can be lowered by
an order of magnitude by porting them to C and the scalar multiplications
can still be sped up by implementing GLV decomposition.

Is this also roughly the situation for the BLS curves you're experimenting
with?

[1] https://github.com/Bren2010/bn448

Post by Jeff Burdges

Post by Zooko Wilcox-OHearn
I was totally wrong about this. Our performance bottleneck is in a
path (zk-SNARK proving) that doesn't require pairing operations, so
using a curve which was 2.5 times slower at pairing operations would
not worsen our performance issues. However, if it was also 2.5 slower
for curve operations, then it would.

It's still slower for scalar multiplication due to being a larger curve,
no?
In any case, you said there are no risks to the anonymity here, so an
alternative to changing curves might be to prevent attacks from being
profitable by capping the maximum value in a transaction or account,
right? In the short term, this should not require dong anything.
Jeff
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves

[Michael Scott]

Hello Brendan,


Yes that's roughly my experience. However I would expect the ratio for the
pairing to rise from 2.5 to 1 to maybe 4 to 1 for highly optimised assembly
language implementations (based on some back-of-the-envelope calculations).
I would expect the pairing (and in particular the final exponentiation) to
suffer more than scalar mults in G1 and G2, as there although the field
size must increase, the group size ideally should not. So the impact is
likely to be rather protocol dependent. In a good pairing-based protocol
most of the action should take place in G1, with ideally just one pairing
calculation.


Here is another take on a possible response to the new estimates..

There is an asteroid called "Quantum Computing" heading straight for
"Planet Crypto". We know more or less exactly what damage it will do. And
from what I have been hearing it is expected to hit around the year 2030.

Now if you look at papers estimating key sizes that we would need, often
they were based on extrapolations of current technologies beyond 2050. Well
that's all pretty pointless now. So why beat ourselves up between now and
the asteroid strike? As of now 80 bits of (AES equivalent) security has
still not been broken, and may still be fine in 2030!

Now a 336-bit BLS curve is an ideal fit for 112-bits of security. I suggest
that this would be more than enough to carry us forward to the
end-of-the-world-as-we-know-it.

The current response of the community rather reminds me of the French
response at the end of WW1, which ignored the coming impact of the Tank and
instead built a bigger and better trench system - the Maginot line.


Mike


On Thu, Sep 29, 2016 at 6:21 AM, Brendan McMillion <

Post by Brendan McMillion
Hey Mike,
This morning, I forked Golang's implementation of bn256 and fit it with a
448-bit BN [1] curve based on the parameter
u = 1910986621940954212840033034977453
which, according to ellipticnews, should be closer to the 128-bit security
level. Interestingly, it's also very close to 2.5 times slower than the
same implementation for a 256-bit curve for all major operations. For
scalar mult in G1, 2 milliseconds to 5ms. For scalar mult in G2, 5ms to
13ms. For a pairing, 15ms to 35ms. All of these numbers can be lowered by
an order of magnitude by porting them to C and the scalar multiplications
can still be sped up by implementing GLV decomposition.
Is this also roughly the situation for the BLS curves you're experimenting
with?
[1] https://github.com/Bren2010/bn448

Post by Jeff Burdges

Post by Zooko Wilcox-OHearn
I was totally wrong about this. Our performance bottleneck is in a
path (zk-SNARK proving) that doesn't require pairing operations, so
using a curve which was 2.5 times slower at pairing operations would
not worsen our performance issues. However, if it was also 2.5 slower
for curve operations, then it would.

It's still slower for scalar multiplication due to being a larger curve,
no?
In any case, you said there are no risks to the anonymity here, so an
alternative to changing curves might be to prevent attacks from being
profitable by capping the maximum value in a transaction or account,
right? In the short term, this should not require dong anything.
Jeff
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves

_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves

[Ray Dillinger]

Post by Michael Scott
Here is another take on a possible response to the new estimates..
There is an asteroid called "Quantum Computing" heading straight for
"Planet Crypto". We know more or less exactly what damage it will do. And
from what I have been hearing it is expected to hit around the year 2030.
Now if you look at papers estimating key sizes that we would need, often
they were based on extrapolations of current technologies beyond 2050. Well
that's all pretty pointless now. So why beat ourselves up between now and
the asteroid strike? As of now 80 bits of (AES equivalent) security has
still not been broken, and may still be fine in 2030!

Post-Quantum security recommendations for symmetric ciphers (the keys to
which are the material that are most of what public-key algorithms are
used to encrypt) recommend 256-bit keys and recommend NOT using AES-256
in particular.

If you're not interested in symmetric-key cryptography that's all you
need to know. If you want to know some general facts about post-quantum
symmetric crypto, and a few very specific facts about AES with keys
longer than 128 bits, then keep reading.

Always keep in mind that for both public-key and symmetric algorithms,
the crypto code in an application is almost never the weakest security
link unless the algorithm is proprietary or original to the program's
authors. To make the crypto strong enough has become very easy. To make
breaking it the easiest way to break security remains very hard.

That said: In the case of quantum computers, symmetric-key cryptography
is generally, regardless of algorithm, expected to "lose" about half its
key length for purposes of calculating security due to Grover's Algorithm.

80 bits of symmetric-cipher security in a post-quantum world is
therefore expected to be equal in work factor to 40 bits of security in
the pre-quantum world. IE, terribly easy to break.

Current recommendations for long term security in symmetric ciphers use
128 bit keys. But that's long term in the absence of Quantum Computers.
Those who consider Quantum Computers to be likely are extending that to
256 bit keys.

However, AES has been shown to have poor key schedules for keys larger
than 128 bits, and is not recommended at larger key sizes. AES-256 for
example is theoretically less secure than AES-128 if a related-key
attack can be used.

While there are no realistically conceivable scenarios where the
related-key attack could be practically applied, attacks only get
better, never worse, and Quantum Computers are more likely to speed that
process up than slow it down. So why use something where a known attack
exists when things not subject to any equivalent attack are available?

Finally according to the Snowden Files there is an attack on AES using
something called the "Kendall Tau Rank Correlation Coefficient" which
the NSA considered likely to be possible but had not yet successfully
developed at the time of the Snowden leaks. I don't know anything about
it, and fear the unknown.

Summary: Don't build systems with AES keys larger than 128 bits. For
equivalent post-quantum security overengineering, (and this really is
overengineering) build software using some other symmetric cipher with a
256 bit key.


"The More You Know...."

Bear

PS. "... cryptography is like a nice solid security door. It looks
nice, it makes owners feel secure, and it discourages stupid burglars.
But responsible builders, and smart burglars, should notice when it's
installed in a wood framed building with big glass windows."

[Ray Dillinger]

Post by Ray Dillinger
Post-Quantum security recommendations for symmetric ciphers (the keys to
which are the material that are most of what public-key algorithms are
used to encrypt) recommend 256-bit keys and recommend NOT using AES-256
in particular.

Hi Ray,
Section 2, "Symmetric Encryption" recommends AES-256 and Salsa20 with
https://pqcrypto.eu.org/docs/initial-recommendations.pdf
Though it's not an ECC issue, and maybe I misunderstood what you wrote.
Nicolai

It's known (though maybe not well-known) that AES has key
schedule problems over 128 bits.

https://en.wikipedia.org/wiki/Advanced_Encryption_Standard

mentions in passing that there's a related-key attack on AES-256
with a complexity on the order 2^99.5. Which doesn't work on
AES-128. So, oddly, yes there is one known attack vs which
AES-256 is weaker than AES-128. This doesn't apply to any
other attack on AES ever discovered, and all other attacks
have been pretty trivial. (they add up to maybe 2 or three
bits now? Maybe not even that much?)

Here's the first of two IACR papers about it.

http://eprint.iacr.org/2009/317

The other one (which identifies a vanishingly small class of
keys for which the attack is only on the order 2^45) is in
the CRYPTO 2009 printed journal.

Being able to use this "attack" almost requires you to be able to
choose your opponent's keys, which makes it NEARLY useless.

The odds are deeply against anyone being able to actually use a
related-key attack in practice without being able to use a
"chosen-key attack" ("chosen key attack" is a joke, like DOUBLE
encrypting with ROT13 for more security). Especially since the
work factor is still on the 2^99 level, well beyond current
capabilities.

But - in my opinion - if you're going to use 196 or 256 bit keys,
there should be *NO* attack that has less than 2^~194 or 2^~254
complexity. Attacks always get better not worse, and I'm not
sure whether some extremely clever person with quantum computers
will be able to leverage such a "nearly useless" attack in a
surprising way.

So I don't really care if pqcrypto.eu.org recommends it. I don't.
Especially in a post-quantum-computer universe, if that comes
to pass.

All that said, there is absolutely nothing wrong with AES-128
as far as anybody's been able to tell, and as far as we can
tell the larger versions deliver fully in every OTHER way. I
do still recommend AES-128 if you want symmetric ciphers with
128-bit keys.


Bear

[Watson Ladd]

Post by Michael Scott
Hello Brendan,
Yes that's roughly my experience. However I would expect the ratio for the
pairing to rise from 2.5 to 1 to maybe 4 to 1 for highly optimised assembly
language implementations (based on some back-of-the-envelope calculations).
I would expect the pairing (and in particular the final exponentiation) to
suffer more than scalar mults in G1 and G2, as there although the field size
must increase, the group size ideally should not. So the impact is likely to
be rather protocol dependent. In a good pairing-based protocol most of the
action should take place in G1, with ideally just one pairing calculation.
Here is another take on a possible response to the new estimates..
There is an asteroid called "Quantum Computing" heading straight for "Planet
Crypto". We know more or less exactly what damage it will do. And from what
I have been hearing it is expected to hit around the year 2030.

This assumes a relatively large amount of progress in engineering. It
is unclear if this actually possible.

Post by Michael Scott
Now if you look at papers estimating key sizes that we would need, often
they were based on extrapolations of current technologies beyond 2050. Well
that's all pretty pointless now. So why beat ourselves up between now and
the asteroid strike? As of now 80 bits of (AES equivalent) security has
still not been broken, and may still be fine in 2030!

There are several ways to interpret "still not been broken". One is to
look at the largest public computation which has taken place aimed a
crypto challenge. The other is to look at the cost of ongoing
computations. Globally Bitcoin hashing carries out 300*10^15 SHA-256
calculations per second, and thus could compute 7 SHA-1 collisions per
year. This has the same computation cost as breaking an elliptic curve
with 160-bit field
length. Every 3 years another 2 bits are added to the performance per
price. 18 years from now 92 bits will not

There are good reasons to believe that the performance of the number
field sieve variants used in these new attacks can increase. These
include the continuing rate of new results, the absence of sound
theoretical lower bounds, and the persistence of worse performance in
medium fields. Furthermore, these attacks are batchable. In some cases
a single key can be broken to enable forgery, such as in SNARKS.

Post by Michael Scott
Now a 336-bit BLS curve is an ideal fit for 112-bits of security. I suggest
that this would be more than enough to carry us forward to the
end-of-the-world-as-we-know-it.
The current response of the community rather reminds me of the French
response at the end of WW1, which ignored the coming impact of the Tank and
instead built a bigger and better trench system - the Maginot line.

<military history correction>

The Maginot line was not attacked with tanks but bypassed and
besieged, and surrendered after there was no point in fighting. It had
adequate artillery and anti-tank weapons. What did them in was the
assault via the Ardennes, crossing rough terrain with combined arms.
German tanks were inferior in armored warfare, with insufficient
firepower, poor maintainability, and lack of sloped armor. What the
Panzercorps had were innovative commanders and an army capable of
using them to full advantage.

</military history correction>

Post by Michael Scott
Mike
On Thu, Sep 29, 2016 at 6:21 AM, Brendan McMillion

Post by Brendan McMillion
Hey Mike,
This morning, I forked Golang's implementation of bn256 and fit it with a
448-bit BN [1] curve based on the parameter
u = 1910986621940954212840033034977453
which, according to ellipticnews, should be closer to the 128-bit security
level. Interestingly, it's also very close to 2.5 times slower than the same
implementation for a 256-bit curve for all major operations. For scalar mult
in G1, 2 milliseconds to 5ms. For scalar mult in G2, 5ms to 13ms. For a
pairing, 15ms to 35ms. All of these numbers can be lowered by an order of
magnitude by porting them to C and the scalar multiplications can still be
sped up by implementing GLV decomposition.
Is this also roughly the situation for the BLS curves you're experimenting
with?
[1] https://github.com/Bren2010/bn448

Post by Jeff Burdges

Post by Zooko Wilcox-OHearn
I was totally wrong about this. Our performance bottleneck is in a
path (zk-SNARK proving) that doesn't require pairing operations, so
using a curve which was 2.5 times slower at pairing operations would
not worsen our performance issues. However, if it was also 2.5 slower
for curve operations, then it would.

It's still slower for scalar multiplication due to being a larger curve,
no?
In any case, you said there are no risks to the anonymity here, so an
alternative to changing curves might be to prevent attacks from being
profitable by capping the maximum value in a transaction or account,
right? In the short term, this should not require dong anything.
Jeff
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves

_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves

_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves