Paper 2020/520

MMSAT: A Scheme for Multimessage Multiuser Signature Aggregation

Yarkın Doröz, Jeffrey Hoffstein, Joseph H. Silverman, and Berk Sunar


Post-Quantum (PQ) signature schemes are known for large key and signature sizes, which may inhibit their deployment in real world applications. In this work, we construct a PQ signature scheme MMSAT that is the first such scheme capable of aggregating unrelated messages signed individually by different parties. Our proposal extends the notion of multisignatures, which are signatures that support aggregation of signatures on a single message signed by multiple parties. Multisignatures are especially useful in blockchain applications, where a transaction may be signed by multiple users. The proposed construction achieves significant gains in bandwidth and storage requirements by allowing aggregation of unrelated transactions. Our construction is derived by extending the PASS scheme, and thus the security of our scheme relies on the hardness of the Vandermonde-SIS problem. When aggregated, a signature consists of two parts. The first part is a post-quantum size signature that grows very slowly, scaling by on the order of~$\log{K}$ bits for~$K$ signatures. The second part scales linearly with~$K$, with a very short fixed cost, roughly twice the bit security. Thus even when aggregating a modest number of signatures, the per signature cost of MMSAT is in line with that of traditional pre-quantum signature schemes such as ECDSA. As an extension to MMSAT, we describe a variant called MMSATK in which it the public keys required to verify an aggregated signature are compressed by a factor of~$20$ to~$30$.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Digital signaturePASSsignature aggregationcompressed key
Contact author(s)
ydoroz @ wpi edu
jhoff @ math brown edu
jhs @ math brown edu
sunar @ wpi edu
2020-05-05: received
Short URL
Creative Commons Attribution


      author = {Yarkın Doröz and Jeffrey Hoffstein and Joseph H.  Silverman and Berk Sunar},
      title = {MMSAT: A Scheme for Multimessage Multiuser Signature Aggregation},
      howpublished = {Cryptology ePrint Archive, Paper 2020/520},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.