An Efficient and Provably Secure Pairing-Free Certificateless Signature Scheme Based on Variant of RSA

Through the application of certificateless signature, certificate management in traditional signatures can be simplified. Furthermore, the key escrow problem in identity-based signatures can be solved as well. As history has shown, there has not been a general pairing-free certificateless signature scheme which is mainly designed with modular exponentiation and modular multiplication that can possess resistance to Type I and Type II adversaries so far. Therefore, a new hard mathematic problem is firstly defined in this paper, which is called variant of RSA problem. In the next step, a new general pairing-free certificateless signature scheme is proposed based on the newly defined variant of RSA problem and the well known discrete logarithm problem. Fortunately, the proposed scheme is also the first RSA-based certificateless signature scheme that can possess resistance to Type I and Type II adversaries. In addition, a formal security proof is provided to demonstrate that, under adaptively chosen message attacks, the proposed scheme is provably secure against Type I and Type II adversaries in the random oracle model. When compared with other known pairing-free certificateless signature schemes of the same type, the computation cost of our scheme is slightly higher, however, a higher security level can be achieved.