Paper 2018/417

On the Provable Security of Two-Round Multi-Signatures

Manu Drijvers and Kasra Edalatnejad and Bryan Ford and Gregory Neven

Abstract

A multisignature scheme allows a group of signers to collaboratively sign a message, creating a single signature that convinces a verifier that every individual signer approved the message. The increased interest in technologies to decentralize trust has triggered the proposal of highly efficient two-round Schnorr-based multisignature schemes designed to scale up to thousands of signers, namely CoSi by Syta et al. (S&P 2016) and MuSig by Maxwell et al. (ePrint 2018). Previous two-round Schnorr-based schemes by Bagherzandi et al. (CCS 2008) and Ma et al. (DCC 2010) are less efficient in terms of signature size, signing time, or verification time. In this work, we prove that none of these schemes can be proved secure without radically departing from currently known techniques. Namely, we show that if the one-more discrete-logarithm problem is hard, then no algebraic reduction exists that proves any of these schemes secure under the discrete-logarithm or one-more discrete-logarithm problem. We point out subtle flaws in the published security proofs of each of the above schemes (except CoSi, which was not proved secure) to explain the contradiction between our result and the existing proofs.

Note: The first version of this work contains a flaw in the security proof of DG-CoSi. This version removes DG-CoSi and expands the negative results.