Use a stronger key splitting?

[burdges]

Any BLS signature library needs key splitting since afaik no constant-time pairing libraries exist, well not everyone believes the amcl claims. We do not care about the pairing itself being constant time of course, but we do signatures on the curve over an extension field, and the extension field arithmetic is not constant time.

What should our key splitting look like?

In this crate, I've used the simple aH(m) + bH(m) with a + b = s rerandomized before each signature in https://github.com/w3f/bls/blob/master/src/single.rs#L158-L189

Yet, much stronger approaches exist like a*(H(m)-X) + b*(H(m)-Y) + (aX+bY) with the (aX+bY) precomputed in the previous signature, and X, Y, and a+b=s rerandomized. In this variant, the attacker knows literally nothing about any of the inputs to the dangerous * operations, not even the point. So

/// We sign using the formula a*(H(m)-X) + b*(H(m)-Y) + (a*X+b*Y) where
/// a, b, X, Y are chosen randomly subject to a + b being our actual secret key,
/// and (a*X+b*Y) being precomputed.
pub struct SecretKey<E: EngineBLS> {
    /// [a, b]
    secrets: [E::Scalar; 2],
    /// [X, Y]
    points: [E::SignatureGroup; 2],
    /// (a*X+b*Y)
    previous: E::SignatureGroup,
}

In between, I suppose a*(H(m) - X) + b*(H(m)+X) + (a-b)*X sounds quite reasonable, so

pub struct SecretKey<E: EngineBLS> {
    a: E::Scalar,
    b: E::Scalar,
    x: E::SignatureGroup,
    y: Option<E::SignatureGroup>, // (a-b)*x
}

There are two extra scalar multiplications in the first, but only one in the second, but the second ties this scalar multiplication to the current values of a and b while the first permits leaving either a and b or X and Y fixed for longer periods.

Importantly, these extra scalar multiplications could be done in another thread, so the second requires resplit to clear y, but now resplit should be called after sign_once and another function that precomputes y should be called in between resplit and the next sign_once.

[burdges]

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.

[burdges]

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..

[burdges]

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..

[liamsi]

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).

[burdges]

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.

[burdges]

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.