Key points are not available for this paper at this time.
Aggregate signature (AS) allows non-interactively condensing multiple individual signatures into a compact one. Besides faster verification, it is useful to reduce storage and bandwidth, and is especially attractive for blockchain and cryptocurrency. In this work, we first demonstrate the subtlety of achieving AS from general groups, by a concrete attack that actually works against the natural implementations of AS based on almost all the variants of DSA and Schnorr's. Then, we show that aggregate signature can be de- rived from the -signature scheme proposed by Yao, et al. To the best of our knowledge, this is the first aggregate signature scheme from general elliptic curves without bilinear maps (in particular, the secp256k1 curve used by Bitcoin). The security of aggregate -signature is proved based on a new assumption proposed and justified in this work, referred to as non-malleable discrete-logarithm (NMDL), which might be of independent interest. When applying the resultant aggregate -signature to Bitcoin, the storage volume of signatures reduces about 49.8%, and the signature verification time can even reduce about 72%. Finally, we specify in detail the application of the proposed AS scheme to Bitcoin, with the goal of maximizing performance and compatibility. We adopt a Merkle-Patricia tree based implementation, and the resulting system is also more friendly to segregated witness and provides better protection against transaction malleability attacks.
Yunlei Zhao (Tue,) studied this question.