New paper on proving security of multi- and threshold signatures (MuSig2 and Frost)

Proving the security of Schnorr multi/threshold signatures is notoriously difficult (due to concurrency). We just put out new work on improved techniques to prove security of these schemes, and use these techniques to prove the security of MuSig2 and FROST

Proofs of security for these schemes in the past had subtle bugs by overlooking a concurrent adversary. Existing proofs that do consider concurrent adversaries are extremely complex, and so having a simplified framework ensures that thoughtful analysis/review is easier to provide.

Most interestingly, our proof techniques allow us to prove *more efficient* variants of MuSig2 and FROST; we are able to reduce the number of group operations from linear in the number of signers to constant. The schemes we prove are the most efficient to date in the literature.

The performance improvements shown in this new work by Elizabeth Crites, Chelsea Komlo, and myself will be incorporated into the next FROST CFRG draft update.

Code for this project can be found here.