Achieving High Efficiency in Schnorr-Based Multi-Signature Applications in Blockchain

Multi-signature applications allow multiple signers to collaboratively generate a single signature on the same message, which is widely applied in blockchain to reduce the percentage of signatures in blocks and improve the throughput of transactions. The k-sum attacks are one of the major challenges in designing secure multi-signature schemes. In this work, we address k-sum attacks from a novel angle by defining a Public Third Party (PTP), which is an automatic process that can be verifiable by the public and restricts the signing phase from continuing until receiving commitments from all signers. Further, a two-round multi-signature scheme HEMS with PTP is proposed, which is secure based on the discrete logarithm assumption in the random oracle model. As each signer communicates directly with the PTP instead of other co-signers, the total amount of communication is significantly reduced. In addition, as PTP participates in the computation of the aggregation and signing algorithms, the computation cost left for each signer and verifier remains the same as the basis Schnorr signature. To the best of our knowledge, this is the high efficiency that a Schnorr-based multi-signature scheme can achieve. Further, HEMS is applied in a blockchain platform, e.g., Fabric, to improve transaction efficiency.