Cheon's attack and its effect on the security of big trusted setups

Is it safe to say that a takeaway from this is to stick with the well-used and audited curves and use updateable SNARK schemes?

For each doubling of d you loose half a bit of security. For realistic upper bounds for d, say 2^{30}, you would need only +15 bits in the order to compensate.

But what about the d \vert p - 1 requirement? If I look at the factorization of p-1 for the BN254 curve (please check that I got the order right, it’s strangely hard to find concrete parameters for BN254 online):

2^3 \cdot 3 \cdot 1279341515037335760923230309485547607615095952161030647804445804731813728599

The final factor is > 2^{249}, so can not appear in d, that leaves the highest choice for d as 24, which gives an attack complexity of 2^{127.32}, i.e. we only loose negligible 0.7 bits of security.

Edit: Looks like a variant mention in the paper works for d \vert p + 1, which factors as:

2 \cdot 31 \cdot 485115557 \cdot 1020847438134909471455349635706891684178805671318695707584770673967

2^{28} < 485115557 < 2^{29} so only Perpetual Powers of Tau should be worried?

1 Like

The p - 1 is of the group order p = 21888242871839275222246405745257275088548364400416034343698204186575808495617, which has a 2^{28} factor in it. Since we’re talking about the curve prime subgroup order, this affects all of the curves that we mentioned.

And yeah, the +40 bits is just an example of something that definitely negates this attack, we can probably use something smaller if we care more about efficiency than a higher safety margin.

2 Likes

Ah, yes, that makes p-1 and p+1 pretty smooth numbers.

As an alternative mitigation strategy (for sake of curiosity, bumping the size is probably the way to go), how realistic would it be to look for a curve where p-1 and p+1 have mostly large factors?

1 Like

p+1 doesn’t necessarily have to be pretty smooth. For example, if p-1 has a large 2^n factor, p+1 won’t.

The problem with having p-1 with mostly large factors is that FFTs won’t be as efficient. It’s common today to use a radix-2 FFT (or multi-radix in the case of Coda), where you use the small factor in each step of the recursion

1 Like

This doesn’t seem right. “alt-bn128” has less than 100 bits of security (not 110, as the OP linked) against NFS.

BLS12-381 has about 117-120 bits of security under the same attack – which seems pretty close to the effect that Cheon’s attack has with Sapling’s setup.

3 Likes

As a side note I expect we’ll be able to easily go beyond d=2^{30} with hardware acceleration, and that there will be demand for these larger circuits. My very rough guesstimate based on preliminary VDF ASIC numbers is that one could build a 1 Watt core that does elliptic curve addition in ~1ns. So given a rig with 256 such cores one could do about 2^{30} multiexponentiations per second.

The other computational (and memory) bottleneck is FFTs but I believe we can tradeoff FFTs for multiexponentiations for SNARKs such as PLONK and SLONK (writeup to be published soon). As such, I’d set d=2^{40} as a more realistic upper bound :slight_smile:

2 Likes

Note that we did consider this attack during the design of Sapling / BLS12-381. I seem to remember we came to similar conclusions then to what @ebfull says above, i.e. that it’s not a significantly better attack than TNFS against Sapling. Of course it does have a greater effect for larger d.

[Edited 2021-09-03: according to the security estimates for STNFS at Pairing-friendly curves – Aurore GUILLEVIC and the code at tnfs-alpha / alpha · GitLab, the security of BLS12-381 against STFNS is ~126 bits. So the Cheon attack for trusted setups using BLS12-381, e.g. Sapling’s setup, does give a security level lower by a few bits (see below) than STNFS, although it is not lower than we previously conservatively estimated for STNFS.]

1 Like

I think it popped out of our heads, at least mine, for a little while, otherwise we wouldn’t have claimed bls-381 has 128 bits security here https://electriccoin.co/blog/new-snark-curve/.

I think it’s hard to really estimate the best nfs attack. Generally speaking
you’re moving to a field of ~4000 bits instead of 3000 bits in bls vs bn254; so it should give you something

3 Likes

I think quite a bit of time elapsed between when we first settled on BLS12-381 (the blog post) and when we actually finished designing Sapling, which was roughly when we started looking closer at NFS and e.g. the NCC audit finished. We concluded that there wasn’t another curve for us to move to that gave a sufficient security boost without significant performance loss.

2 Likes

Thanks for the correction on the security of “alt-bn128”, I was looking at old results.

The focus of the post is indeed larger setups than Sapling’s Powers of Tau (like I mentioned in another reply) - there are pretty large setups in the wild at the moment.

2 Likes

Don’t the Coda curves have much larger groups, so that this attack is not significant?

1 Like

For BLS12-381 in Sapling, d = 2^{21}, so we have 2^{117.2} exponentiations in the subgroup of d'th powers in \mathbb{F}_p^* which should have the same cost as roughly 255 \cdot 2^{117.2} \approx 2^{125.2} \mathbb{F}_p^* multiplications. Sapling had a design strength of \sim\!125 bits (limited by the 251-bit hash \mathsf{CRH^{ivk}} and the subgroup size of Jubjub). Yes the blog post and/or the protocol spec should mention the Cheon attack, even if only to say that it isn’t a problem for Sapling. I’ve opened a ticket.

(It’s reasonable to measure the cost in multiplications, because the cost of square-root DL attacks is normally measured in group operations which are comparable, to within a small constant factor, to multiplications in \mathbb{F}_p^*. More precisely a group operation takes about 9 to 14 \mathbb{F}_p multiplications, so [for comparison with Pollard rho or Pollard kangaroo] the 2^{125.2} \mathbb{F}_p^* multiplications above correspond to at least 2^{122} group operations.)

[Edited 2021-09-03 to give a more precise estimate accounting for d = 2^{21} for the Sapling setup, not 2^{27} as in the Filecoin setup.]

For historical interest, let’s also compute this for BN-254 in Sprout. Again d = 2^{21}, but the group order is slightly smaller, so we have 2^{116.6} exponentiations in the subgroup of d'th powers in \mathbb{F}_p^* which should have the same cost as roughly 254 \cdot 2^{116.6} \approx 2^{124.6} \mathbb{F}_p^* multiplications. For comparison with Pollard rho or Pollard kangaroo, this would correspond to at least 2^{121.4} group operations.

2 Likes

Oh, you’re right, they do, about 750 bit groups. Definitely not relevant there :slight_smile:

1 Like

Just to clarify, the smoothness of other factors of p-1 and p+1 doesn’t matter. The Cheon algorithm can only compute the \tau for which \{g, g^\tau, g^{\tau^d}\} is given [corrected], and in the zk-SNARK context, that is only given up to the d determined by the setup. There is indeed a variant of the algorithm that works with p+1, but only if g^{\tau^{0..2d}} is given for d a factor of p+1. In the zk-SNARK context that variant doesn’t help because p+1 will not be highly 2-adic, and even if it were we don’t have any extra g^{\tau^i} available.

2 Likes

Small note - for the p-1 variant, we only need g, g^\tau g^{\tau^d}, and not the elements in between. In the zk-SNARK context we indeed have them though.

2 Likes

though there’s no concrete attack for now using smoothness of other factors, intuitively it feels safest to me to have a p-1 that just has a large prime factor besides the power of 2 used for the FFT. So I wonder if we could construct a curve like that.

Can you explain the intuition? I haven’t before seen anyone suggesting we need to care about factors of p-1 for security reasons, either in pairing or non-pairing curves.

(An extreme case for example is NIST P224:

sage: factor((2^224 - 2^96 + 1)-1)
2^96 * 3 * 5 * 17 * 257 * 641 * 65537 * 274177 * 6700417 * 67280421310721

)

Well the basic attack of Cheon requires a small factor of p-1. Moreover, Corollary 1 in Cheon’s paper, gives improved run time compared to the main attack, when the attacker possesses g^{a^{(p-1)/d}} for each factor d, and the run time is dominated by sqrt(d) for largest prime factor d. The specific attack in cor 1 is not of concern cause it requires such high powers of tau, but generally there’s more subgroups to play with when you have many small factors (credit: some of this intuition relates to thoughts shared with me by others while trying to improve Cheon)

2 Likes

This new [Guillevic19] paper revises all the recent security estimations with respect to the Special TNFS attack on pairing-friendly elliptic curves due to Barbulescu, El Mrabet et Ghammam [DEG19], Fotiadis and Konstantinou [FK18] and Fotiadis and Martindale [FM19]. It concludes that for 128-bit security with the fastest pairing one should consider BLS12 over 440 to 448 bits or or a Fotiadis–Martindale curve of embedding degree k=12, discriminant D=3 and twist of degree 6 over a 446-bit prime. I implemented this curve as BW12-446 here and it has a subgroup of order 296-bit and a 2-adicity s=37. So with respect to Cheon’s attack, for the biggest setup (Perpetual Powers of Tau), this translates to 1.25(\sqrt{\frac{2^{296}}{2^{28}}}+\sqrt{2^{28}}) \approx 2^{134} exponentiations in \mathbb{G}_1.

5 Likes