Abstract: Certificateless cryptosystem became more and more popular because it eliminates the complicated certificates management in PKI and the keys escrow problem.However,it shows poor efficiency because it based on bilinear pairs.A new certificateless signature scheme without paring is proposed,which based on ElGamal algorithm.The ElGamal algorithm can eliminate the bilinear pairs operation,and then the security proofs of signature scheme has been described by Random Oracles Model.The security vulnerability in existing schemes has been avoided in our scheme.Analysis result shows that both the amount of calculation in verification process and the signature length have been reduced by 20 and 33.3,respectively,compared with the existing scheme.