In ubiquitous computing, data should be able to be accessed from any location, and the correctness of data becomes vital during the communication. Suppose that many users sign different messages respectively, before forwarding or sending these messages, then the verifier must spend a lot of computing time to verify their signatures. Consequently, the aggregate signature scheme is an effective method of improving efficiency in this kind of systems, which provides the convenience for the verifier. In this paper, we propose a new certificateless aggregate signature scheme which is efficient in generating a signature and verification. This scheme is provably secure under the extended computational Diffie-Hellman assumption.