Add threshold (multi)signatures

[burdges]

I believe the most advanced threshold signature implementation is https://github.com/poanetwork/threshold_crypto but they do not provide our abstractions, and one should optimize the arithmetic ala poanetwork/threshold_crypto#13 We should do threshold signatures in a way that supports #4 if possible. All this sounds doable if threshold signatures are provided in a way that exploits the current aggregation abstraction, but it's worth considering any parallels with w3f/schnorrkel#11 too.

[burdges]

There is a lot of literature on this topic, including fairly applied things like https://eprint.iacr.org/2017/216.pdf but some literature notes singled out by @Daeinar

[1] Secure Distributed Key Generation for Discrete-Log Based Cryptosystems (see attachment, only accessible behind a paywall unfortunately)

[2] Distributed Key Generation in the Wild (https://eprint.iacr.org/2012/377.pdf)

[3] Verifiable Secret Redistribution for Archive Systems (see attachment, only accessible behind a paywall unfortunately)

[4] Fully Distributed Non-Interactive Adaptively-Secure Threshold Signature Scheme with Short Shares: Efficiency Considerations and Implementation (https://csrc.nist.gov/CSRC/media/Events/NTCW19/papers/paper-LJYM.pdf)

[1] is the starting paper you probably want to read which presents the basic Pedersen DKG, an "attack" on it when there’s an active adversary, and an improved but much more complex version, the Rabin DKG, that amends the “flaw” in the Pedersen DKG. Both of those DKGs work in a partially synchronous network. The "flaw" in the Pedersen DKG allows an active adversary to bias a bit the distribution from which the shared public key is generated as far as I remember. There was also a remark somewhere (can’t remember where unfortunately) saying that this “flaw” is not really problematic if you're using the Pedersen DKG to setup a threshold signing system. I can check if I can find that reference.

[2] presents an improvement over [1] where you can run the DKG over a fully asynchronous network which is quite cool as it basically resembles how communication on the Internet works. However, to use this you need to implement a non-standard secret sharing scheme that works with two variables instead of one. I am not aware of any library that gives you this functionality, so it’s very likely that you would need to implement that from scratch.

[3] shows how you can do a re-distribution of your secret, meaning that you can completely change the underlying group of trustees and the secret sharing threshold while keeping the initially established public value the same. In other words, lets say a first group of n nodes runs a DKG with threshold t to establish a shared secret s (which is unknown to the individual nodes) and its public counterpart (key) p, then you can re-share it to a config (n’, t’, s, p) where n and n’, t and t’ do not have to be the same necessarily while p stays fixed. Note that while the shared secret s also stays the same, it gets re-shared and thus the individual shares that each node computes during re-sharing are different from the old ones. This gives you obviously a lot of flexibility because now you can change the entire configuration of your trustee group and swap out nodes that have become unresponsive or corrupted or add new nodes to strengthen the robustness of the trustee group. Additionally, it gives you forward security when honest nodes delete their old shares after the re-sharing has finished.

To see this in action you can check out our drand project (https://github.com/dedis/drand), a threshold BLS randomness beacon (announced a while ago in Cloudflare’s crypto week: https://www.cloudflare.com/leagueofentropy/) where we use a Pedersen DKG from [1] for the setup and the re-sharing feature from [3] to change the configuration of the nodes that produce the public randomness. Note, however, that implementing [3] is quite complex and if your system can work in a scenario where the public key p changes from time to time (i.e., you re-run the DKG) then I would probably advise to do that instead of re-sharing. For example, the drand re-sharing feature still has a bug somewhere such that the re-sharing fails from time to time when we do it over the live network while it works perfectly when we do it “offline” (oh the joys of distributed computing :)). So when you are publishing the shared public key p on a blockchain and your only application is threshold signing then that should be fine I guess. If you also need threshold encryption to manage encrypted data on the long-term, then that’s a different story because there you really don't want to change your public key otherwise you have to re-encrypt your archive every time the key changes.

[4] is a nice paper on threshold signing and the current state of the art as far as I know.

From a (purely academic) research perspective it might be interesting to see what it takes to design a re-sharing scheme [3] for a fully asynchronous DKG [2], btw. I am not aware that anything like that exists.

I'd love it if we can keep this code parallel with w3f/schnorrkel#11 but maybe not so easy.