Chang-An Zhao

2016-10-08 02:18:30 UTC

Hi,Zooko，

Do you have an exact citation for this claim of "BN128 still has at least 96 bits of security"? or any other experts can provide more information for me?

I mean that BN128(take base field p have 256 bits about) was designed for AES-128 bit security. Now due to the progress of NFS algorithm, the security may be not attained. But where can I find this claim of "BN128 still has at least 96 bits of security"?

Best regards

-----------------------------------------

Chang-An Zhao

-----------------------------------------

Department of Mathematics,

Sun Yat-sen University,

P.R. China.

-----------------------------------------

----- Original Message -----

From: curves-***@moderncrypto.org

To: ***@moderncrypto.org

Sent: Tuesday, 27 September, 2016 3:00:01 AM

Subject: Curves Digest, Vol 235, Issue 1

Send Curves mailing list submissions to

***@moderncrypto.org

To subscribe or unsubscribe via the World Wide Web, visit

https://moderncrypto.org/mailman/listinfo/curves

or, via email, send a message with subject or body 'help' to

curves-***@moderncrypto.org

You can reach the person managing the list at

curves-***@moderncrypto.org

When replying, please edit your Subject line so it is more specific

than "Re: Contents of Curves digest..."

Today's Topics:

1. Re: Curves for pairings (Zooko Wilcox-OHearn)

----------------------------------------------------------------------

Message: 1

Date: Sun, 25 Sep 2016 23:58:05 +0000

From: Zooko Wilcox-OHearn <***@leastauthority.com>

To: Michael Scott <***@miracl.com>

Cc: "***@moderncrypto.org" <***@moderncrypto.org>

Subject: Re: [curves] Curves for pairings

Message-ID:

<***@mail.gmail.com>

Content-Type: text/plain; charset=UTF-8

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

Regards,

Zooko Wilcox

Founder and CEO

https://LeastAuthority.com — Freedom matters.

------------------------------

Subject: Digest Footer

_______________________________________________

Curves mailing list

***@moderncrypto.org

https://moderncrypto.org/mailman/listinfo/curves

------------------------------

End of Curves Digest, Vol 235, Issue 1

**************************************

Do you have an exact citation for this claim of "BN128 still has at least 96 bits of security"? or any other experts can provide more information for me?

I mean that BN128(take base field p have 256 bits about) was designed for AES-128 bit security. Now due to the progress of NFS algorithm, the security may be not attained. But where can I find this claim of "BN128 still has at least 96 bits of security"?

Best regards

-----------------------------------------

Chang-An Zhao

-----------------------------------------

Department of Mathematics,

Sun Yat-sen University,

P.R. China.

-----------------------------------------

----- Original Message -----

From: curves-***@moderncrypto.org

To: ***@moderncrypto.org

Sent: Tuesday, 27 September, 2016 3:00:01 AM

Subject: Curves Digest, Vol 235, Issue 1

Send Curves mailing list submissions to

***@moderncrypto.org

To subscribe or unsubscribe via the World Wide Web, visit

https://moderncrypto.org/mailman/listinfo/curves

or, via email, send a message with subject or body 'help' to

curves-***@moderncrypto.org

You can reach the person managing the list at

curves-***@moderncrypto.org

When replying, please edit your Subject line so it is more specific

than "Re: Contents of Curves digest..."

Today's Topics:

1. Re: Curves for pairings (Zooko Wilcox-OHearn)

----------------------------------------------------------------------

Message: 1

Date: Sun, 25 Sep 2016 23:58:05 +0000

From: Zooko Wilcox-OHearn <***@leastauthority.com>

To: Michael Scott <***@miracl.com>

Cc: "***@moderncrypto.org" <***@moderncrypto.org>

Subject: Re: [curves] Curves for pairings

Message-ID:

<***@mail.gmail.com>

Content-Type: text/plain; charset=UTF-8

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

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

Curves mailing list

https://moderncrypto.org/mailman/listinfo/curves

--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

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

_______________________________________________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

Regards,

Zooko Wilcox

Founder and CEO

https://LeastAuthority.com — Freedom matters.

------------------------------

Subject: Digest Footer

_______________________________________________

Curves mailing list

***@moderncrypto.org

https://moderncrypto.org/mailman/listinfo/curves

------------------------------

End of Curves Digest, Vol 235, Issue 1

**************************************