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.
References (as a new user, I am restricted to 2 links per comment):
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.]
About that. The subgroup seem more interesting to me. Is this paper about that variant of the attack useful A Group Action on $${\mathbb Z}_p^{\times }$$ and the Generalized DLP with Auxiliary Inputs | Revised Selected Papers on Selected Areas in Cryptography -- SAC 2013 - Volume 8282 or it can’t be applied ?
Considering the discussions you had with Ariel and Zac about finding a curve with a larger group order , how practical do you think it is for projects with high security demands but limited resources to transition to such a curve? I’m also curious whether a 40-bit increase in order , as mentioned , truly offsets the effects of Cheon’s attack without significant performance loss , especially given that other approaches , like moving to updatable SNARK schemes , might also offer a solution.
Though please notice in G_2 that what matter is order-1 instead of the prime group.
In that case things are much smoother.
What are the potential implications of Cheon’s attack on the security of cryptographic protocols that rely on large trusted setups, such as those in zk-SNARK applications, and how could projects mitigate these risks in future trusted setup implementations?