Abstract: In certificateless signature(CLS) based on Al-Riyami frame, the secure condition is key generation center (KGC) which can not implement public key replacement attack. So CI_S can not resist this attack from KGC. A new sig- nature system called certificateless signature without public key replaced was presented. It shows that public key signa- ture for users can resist the public key replacement attack from KGC and raise the security of CI_S to a new level. An instance of constructing this class of certificateless signature scheme based on Al-Riyami frame was afforded. The public key signature was proven unforgery under the random oracle model. I}he method to construct the public key signature can be applied to any certificateless signature schemes based on Al-Riyami frame.

Key words: Bilinear pairing, Certificateless signature, Public key replacement attack, ROM