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
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.
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 
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.]
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
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.
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.
Don’t the Coda curves have much larger groups, so that this attack is not significant?
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.
Oh, you’re right, they do, about 750 bit groups. Definitely not relevant there
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.
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.
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)
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.
Coda is now using a half-pairing cycle with a Marlin/Halo hybrid, which has a powers-of-tau-style setup. However, this still resists Cheon attacks because the pairing-friendly curve of the cycle is 382-bit BN, so its security against Cheon attacks for powers of tau up to \tau^{2^k} would be 1.25 \left(\sqrt{2^{382 - k}} + \sqrt{2^k}\right) exponentiations. I don’t know what power of tau the new Coda setup goes up to, but it would have to be infeasibly large (more than 2^{126}) for Cheon attacks to be significant.
[Edit: this was correct in March 2020, but Mina (as Coda is now called) currently uses the Pasta curve cycle instead, and does not use a trusted setup so Cheon attacks are not applicable at all.]