MMSAT: Lattice-Based Aggregate Signatures
MMSAT: Lattice-Based Aggregate Signatures
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 ~logK 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.
About the speaker
Professor, Brown University
Jeffrey Hoffstein is professor at Brown University, USA. He started his research career in 1978 graduating with a PhD degree from MIT. He was a postoc at the Institute for Advanced Studies in Princeton and at the University of Cambridge. Jeffrey has hold assistant or associate professorships at the University of Rochester and Brown University. His research is focusing on number theory, automorphic forms and cryptography. In collaboration with Jill Pipher and Joseph Silverman he created the widely well-known cryptosystem called NTRU, based on lattices in 1995.