algebra
algebra copied to clipboard
arkworks-rs
Security estimates of pairing-friendly curves
Due to improvements on special towered number field sieves, a recent paper from A. Guillevic show that many pairing-friendly curves are below their targeted level of security. For instance, the paper states that the base field size of BLS12 curves need to be increased up to 446 bit (instead of 377 as for BLS12-377 or (z-Cash's) BLS12-381) to serve 128 Bit security. Furthermore, by personal communication with the author of the above paper, I have also received similar estimates on MNT curves which I uploaded to our repository, see https://github.com/ZencashOfficial/ginger-lib/issues/47. The results are as for the BLS12 curves:
- Coda's MNT4-753 security is about 112 bit, and
- in order to serve 128 Bit security the base field size needs to be increased up to 1024 bit.
Guillevic's note also includes a link to a parameter file of new MNT4/6 cycles with base field size 996 bits and beyond) which serve quite acceptable domain sizes for mixed radix FFT. As we from ginger do not aim at implementing Guillevic's cycle (already Coda's is very slow in performance) I can be of help providing parameters (such as cofactors and non-residues for extension fields) if this is of interest for Zexe.
Are there any new claims about the current security level for BL12-377/381 there? I missed them. Also anything about BN128?
I cannot find explicit security estimates on BLS12 and BN curves with given field size in published paper either, but expect such to be significantly below 128 bits, as the proposed field size of 446 bits (for 128 bit security). I suppose that their explicit estimates can be produced by the scripts on https://gitlab.inria.fr/tnfs-alpha/alpha/tree/master/sage.
These field size recommendations are not new, they are similar to https://eprint.iacr.org/2019/485.pdf, which even propose 460 bit field size for BN curves at 128 bits security (but do not investigate BLS). Both papers do not treat low embedding degrees, Guillevic's above mentioned note on MNT4/6 curves complements that.
Do you have an idea to what extent the security is reduced? The discussion here indicates that the attacks reduce security of BLS12 curves to ~120 bits.
As an aside, using these curves inside SNARKs already reduces their security to <118 bits following Cheon's attack, as described here
Thank you for pointing out the discussion on z-Cash and Cheon's attack. As I do not have concrete numbers, I will have a look at the above mentioned sage scripts (somewhen in near future). I will keep you posted on this.
@yelhousni: Wow, thank you very much! I did not expect the security loss compared to the recommendation from Guillevic 2019 (base field size 446 for 132 bit DL cost) that low. Is there a short explanation for that?
Yes because the analysis takes Cheon's attack into consideration as opposed to [Guillevic19].
Cheon's attack aside, I expected the STNFS cost of the BLS12-377 far below 125 Bit (as the Guillevic 2019 paper recommends 446 bit base field for a comparable security level). But that is maybe due to my lack of understanding how the security estimates are done.