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

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