Round Optimal Secure Multisignature Schemes from Lattice with Public Key Aggregation and Signature Compression

This paper presents the first construction for an efficient multisignature (MS) in the lattice setting, achieving signature compression and public key aggregation simultaneously with single round signature generation. The multisignature size in our construction is the same as that of a single signature. The verification of a multisignature can be performed with the aggregated public key and the verifier gets convinced that the message has been signed by all the signers. More positively, our aggregated public key size is also the same as that of a single signer. Additionally, we extend our multisignature to an accountable subgroup multisignature (ASM) that permits any subset of potential signers to sign a common message with the property that the signature reveals the identities of the signers to any verifier. Our ASM scheme enjoys the same efficiency as that of our MS scheme without incurring any loss in the security reduction. We design our schemes in the plain public key model where there is no need to verify individual public keys. Our constructions are built in the standard lattice and are proven to be secure under the hardness of the short integer solution (SIS) problem in the random oracle model.