  Multi-signature aggregates signatures from multiple users on the same message
into a joint signature, 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 to design 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 MEMS with PTP is proposed, which is secure based on
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 communications 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 maximum
efficiency that a Schnorr-based multi-signature scheme can achieve. Further,
MEMS is applied in blockchain platform, e.g., Fabric, to improve the
transaction efficiency.
