A Novel Certificateless Multi-signature Scheme over NTRU Lattices

Publication Name

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)


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.

Open Access Status

This publication may be available as open access


13107 LNCS

First Page


Last Page


Funding Number


Funding Sponsor

National Natural Science Foundation of China



Link to publisher version (DOI)