Use a stronger key splitting? about bls HOT 6 OPEN

We noticed a nicer trick: Initially set X_0 to be random and compute Z_0 = a X_0 + b X_0 for some random a,b with a+b=s. In signing, set X_{i+1} = H(m) - X_i and compute Z_{i+1} = aX_{i+1} + bX_{i+1} so our signature is z_{i+1} + Z_i. And resplit remains the same. Amortized, this costs zero additional scalar multiplications, just the tow in setup.

You can make this work with distinct X and Y too, but now replit requires an extra scalar multiplication. In Polkadot's GRANDPA, we always signing several messages simultaneously, so our key spiting could maybe exploit this too somehow.

from bls.

I've implemented this last idea in c8db373 because it's basically free. I'll leave this open since we might still consider more radical approaches..

from bls.

Thomas Pornin cautions against viewing key splitting as an alternative to constant-time implementations. We expect librustzcash to eventually become constant-time, so I'm not eger to duplicate their efforts, but maybe worth considering.

Thomas Pornin suggests viewing key splitting more as a defense against attackers in physical proximity, like power analysis and fault attacks. I'd wanted to pull out the key splitting whenever librustzcash becomes constant-time, but maybe we cannot do so due to the broader lack of experience with pairing based protocols. Oh well..

from bls.

I also do not think that key-splitting makes the arithmetic constant time. I'm not too familiar with "physical proximity, like power analysis and fault attacks" but it would be cool if this idea was backed with some empirical evidence of some sense (maybe there is? at least I'm not aware of that).

from bls.

There are many papers on roughly this topic for RSA, including some theoretical models, since people like the CRT optimization which causes big problems. It's hard to have satisfactory answers though because side channel attackers are so diverse, including some from which no crypto sounds safe.

Yes, it definitely does not make arithmetic constant-time per se, but the question is how much the threats overlap. If overlap is large, then key splitting helps avoids duplicating effort with zcash, who rarely take pull requests even for trivial things. If the overlap is small, then we should prioritize constant-time signing, maybe by using specialization to call amcl for signing only, or maybe abstracting EngineBLS further from pairing::Engine and implementing it for some constant-time implementation, which mostly means reimplementing methods those lack.

from bls.

There is recent work on making the zcash libraries constant time in https://github.com/zkcrypto/bls12_381 so I'm inclined to wait for now.

In any case, we're likely stuck with key splitting now due to worries about validators being run on cloud service providers, so..

I picked an additive split here for speed, but a multiplicative split ab=s with sigma = a(b*H(m)) would not be much slower. Do we gain anything from a multiplicative split? I suspect yes maybe.

from bls.