Efficient provable certificateless blind signature scheme

Certificateless public key cryptography is a new paradigm introduced by AI-Riyami and Paterson. It eliminates the need of the certificates in traditional public key cryptosystems and the key escrow problem in Identity-based Public Key Cryptography (ID-PKC). Due to the advantages of the certificateless public key cryptography, we propose a novel certificateless blind signature scheme based on pairings in the paper. Firstly, we give formal security definitions of blindness and unforgeability in our scheme. Then an concrete instance is given and we show that the proposed scheme is provably secure in the random oracle model. The security of our schemes is proven based on the hardness of computational Diffie-Hellman problem and the bilinear pairing inversion Problem (BPI). Finally, by comparing our scheme with Zhang´s scheme in terms of computational cost and the signature size, we show that our scheme is more efficient, since no pairing computation is required in the signing, and only one pairing computation is required in the verifying phase.