What a lovely hat

Paper 2018/068

Simple Schnorr Multi-Signatures with Applications to Bitcoin

Gregory Maxwell and Andrew Poelstra and Yannick Seurin and Pieter Wuille

Abstract

We describe a new Schnorr-based multi-signature scheme (i.e., a protocol which allows a group of signers to produce a short, joint signature on a common message), provably secure in the plain public-key model (meaning that signers are only required to have a public key, but do not have to prove knowledge of the private key corresponding to their public key to some certification authority or to other signers before engaging the protocol), which improves over the state-of-art scheme of Bellare and Neven (ACM-CCS 2006) and its variants by Bagherzandi et al. (ACM-CCS 2008) and Ma et al. (Des. Codes Cryptogr., 2010) in two respects: (i) it is simple and efficient, having only two rounds of communication instead of three for the Bellare-Neven scheme and the same key and signature size as standard Schnorr signatures; (ii) it allows key aggregation, which informally means that the joint signature can be verified exactly as a standard Schnorr signature with respect to a single ``aggregated'' public key which can be computed from the individual public keys of the signers. This comes at the cost of a stronger security assumption, namely the hardness of the One-More Discrete Logarithm problem, rather than the standard Discrete Logarithm problem, and a looser security reduction due to a double invocation of the Forking Lemma. As an application, we explain how our new multi-signature scheme could improve both performance and user privacy in Bitcoin.