Re: [Cfrg] Threshold signatures

[Jeff Burdges <[e-mail]>]

At first blush, I’d think code signing could be accomplished with a set of Ed25519 signatures, no?  How can 64 bytes per signer be any concern when signing code large code blobs?  Also, I’d expect code signing should require accountability, so no threshold signatures anyways, right?


I'll assume however that you actually want an cryptographic multisig that returns only one Schnorr/Ed25519 signature though:

As a rule, you should assume the adversary controls all but one of the signing keys and initiates numerous parallel signing interactions with the remaining honest key.  There are cyber-coins use cases where one party possesses all the shares, which weakens this adversary, but code signing means different parties presumably.

> 1) HSM module: One or both parts of the signature key shares are located in a HSM providing resistance against extraction of the public key. This is an important use case as we want the operation of the HSM to be stateless. The signing algorithm requires multiple rounds, in the first round, the signer commits to a value R_i = r_i..B. In the second round, the value r_i is used. So it is kinda important to construct r_i in such fashion that the HSM can restore it from one round to the next even though it may have performed other operations in the meantime.

You need three round trips here because all published two round trip Schnorr multi-signatures are vulnerable to k-sum forgery attacks: https://eprint.iacr.org/2018/417.pdf  Admittedly these attacks have a high complexity, like 2^45 with open 128 parallel signing queries, so hard but still doable.

Afaik, there are no published stateless protocols either, not sure anything simple exists.  If you abandon stateless then one should enforce correct usage using session types like I did in https://github.com/w3f/schnorrkel/blob/master/src/musig.rs although you could approximate session types in C with opaque pointers and runtime checks though.

We’re working on some new approaches to two round trip versions, but no security proofs yet, and nothing stateless.  I’m afraid the mBCJ signature scheme from that paper kinda sucks in practice.

> Another issue that comes up with HSMs is auditability. The construction of r_i must be auditalble which means it must be deterministic.

I've heard about upcoming work that achieves this for a two round trip stateless protocol, but requires zero-knowlede proofs, presumably of elliptic curve arithmetic, and may or may not really address the threshold situation, and may even exploit the secp256k1 mirror curve.  In other word, you might require another secure curve whose group order is 2^255-19, or maybe some clever CRT games.  Those zero-knowlede proofs run only between the signers, but probably way beyond your smart card.

If you’d accept a trusted setup then a zkSNARK on BLS12-381 could verify numerous RedJubJub signatures (EdDSA).


> I will be looking for co-authors :-)

I’ve an unrelated topic that might interest you if you’re interested in code signing.

> One thing I would like to understand what the security rationale for tying the signature hash value k to the value R is. Because that is what creates the need for a two round protocol.

Almost sounds like you’re asking about the Fiat-Shamir transform that makes an interactive Schnorr identification protocol into a non-interactive Schnorr signature.

You need pairings ala BLS signatures for a one round trip multi-signature scheme.  I donno if anyone proved that but you’ll get nothing from fancy zero-knowlede proof tricks among the signers obviously.  I’d expect BLS smart cards for cyber-coin validators within the next couple years, if not already.

Jeff