Discrete logarithm

Schnorr signature

Pure mathematics

Hash function

Materials science

Digital signature

ElGamal signature scheme

Computer security

Theoretical computer science

Encryption

Cryptocurrency

Merkle signature scheme

Aggregate (composite)

Elliptic curve

Ring signature

Blockchain

Computer science

Elliptic curve cryptography

Public-key cryptography

Signature (topology)

Mathematics

Blind signature

Random oracle

Elliptic Curve Digital Signature Algorithm

Geometry

Composite material

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.

Practical Aggregate Signature from General Elliptic Curves, and Applications to Blockchain