A Novel Scheme of Schnorr Multi-signatures for Multiple Messages with Key Aggregation

A digital signature is essential in verifying the reliability of people and data over networks, such as through web server certificates, authentication, and blockchain technologies. In blockchain, multi-signature signature schemes have recently attracted attention for reducing the amount of data in transactions. While such schemes support only a single message, Interactive Aggregate Signatures (IAS), an extended Schnorr multi-signature scheme, supports some messages under the plain public key model. However, there are three problems with this scheme in certain use cases. We propose a key aggregatable IAS scheme called KAIAS. In contrast to the previous works, KAIAS solves these problems which means that KAIAS (1) includes a verification algorithm using only a single aggregated public key, (2) dynamically signature aggregation, and (3) requires signers to sign only their own messages. Recently, the Schnorr multi-signature scheme has been discussed mainly from its advantages of reducing the size of the signatures in the implementation of Bitcoin. Thus, we also propose a practical application of KAIAS that takes advantage of its feature to aggregate both signatures and public keys with low computational complexity of signing.