A novel identity-based multi-signature scheme over NTRU lattices

Multi-signature is an important technology to compress multiple signatures on the common message into a compact one, thereby reducing the consumption of storage space and transmission bandwidth. Such a cryptographic primitive is widely used in financial applications such as blockchain which requires multiple keys to authorize a transaction. With the advent of quantum computers, traditional multi-signature schemes may no longer be secure as their underlying security assumptions (e.g. RSA or discrete logarithm problems) may not hold anymore. In this paper, we propose a novel identity-based multi-signature (IBMS) scheme over NTRU lattices, which is secure against the attacks of quantum computers. To the best of our knowledge, it is the first lattice-based IBMS scheme. We show that our scheme is provably secure in the random oracle model based on the ring version of the short integer solution assumption (Ring-SIS). Compared with the closely related works in the literature, our scheme enables the signer to select its system identity (such as email address, physical IP address, and etc.) as the public key, which effectively alleviates the certificate management problem in the PKI setting, and takes the advantage of discrete Gaussian distribution instead of uniform distribution to generate secret signing keys and multi-signatures. Besides, our scheme does not require all the system users to setup a trusted common string, which further simplifies the deployment of our scheme in practice.