Abstract: Aggregate signatures allow an efficient algorithm to aggregate n signatures of n distinct messages from n different signers into one single signature. Aggregate signature is useful to save bandwidth and improve the efficiency in verification phase. Certificateless public key cryptography overcomes the complicated certificate management in traditional public key cryptography and key escrow problem in identity based cryptography. In this paper, we present a new efficient certificateless aggregate signature scheme based on the bilinear pairing. The analysis shows that the proposed scheme is proven existentially unforgeable against adaptive chosen message attacks under the computational Diffie-Hellman assumption in the random oracle model. The signature length is only two group elements, which is independent of the number of signers, and the signature needs only four pairings and n scalar multiplications computations in verification phase. Thus, the proposed scheme is more suitable for the applications, in resource-constrained environment.