A Novel Certificateless Multi-signature Scheme over NTRU Lattices

With the help of multi-signature technology, multiple signatures on the same message could be compressed into one compact signature, which is efficient for financial applications such as blockchain for saving storage space and transmission bandwidth costs. Due to the advantage of no certificate and no escrow feature, certificateless signature is widely used in many applications since its introduction in 2003. Unfortunately, traditional signature schemes may face serious security threats with the advent of quantum computers as their underlying security assumptions (RSA or discrete logarithm problems) may no longer hold anymore. Lattice-based cryptography is considered to be quantum secure. Therefore, we propose a novel certificateless multi-signature (CLMS) scheme over NTRU lattices in this paper, which is provably secure in the random oracle model based on the ring version of the short integer solution assumption (Ring-SIS). To the best of our knowledge, our scheme is the first lattice-based CLMS scheme. Compared with closely related works in the literature, our scheme is based on certificateless cryptography, which not only solves the key escrow problem, but also relieves the certificate management problem effectively.