Paper 2020/520
MMSAT: A Scheme for Multimessage Multiuser Signature Aggregation
Yarkın Doröz, Jeffrey Hoffstein, Joseph H. Silverman, and Berk Sunar
Abstract
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$.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Digital signaturePASSsignature aggregationcompressed key
- Contact author(s)
-
ydoroz @ wpi edu
jhoff @ math brown edu
jhs @ math brown edu
sunar @ wpi edu - History
- 2020-05-05: received
- Short URL
- https://ia.cr/2020/520
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/520, 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}, url = {https://eprint.iacr.org/2020/520} }