With the popularity of vehicular ad-hoc networks (VANETs), the secure communications between the vehicle and vehicle as well as between the vehicle and infrastructure have attracted people’s great attention. Vehicle privacy protection (including vehicle identity privacy and location privacy), high mobility, density, and limited bandwidth are also a problem that cannot be negligible. In VANETs, it is necessary to design a message authentication protocol to ensure data transmission security, vehicle anonymity, and unlinkability. Considering the resource-constrained environments, the certificateless aggregate signature (CLAS) scheme can compress $n$ signatures of $n$ messages from $n$ vehicles into a single signature, which reduces the signature verification time and storage overhead at the roadside unit. Based on the aforementioned analysis, we design a fully aggregated conditional privacy-preserving CLAS scheme (CPP-CLAS) for VANETs. Instead of using the expensive bilinear pairings and map-to-point hash function operations, the proposed CPP-CLAS scheme uses the elliptic curve cryptosystem (ECC) and general hash functions. Also, with the use of CLAS technology, the computation and communication cost of the scheme are significantly reduced. In addition, based on the elliptic-curve discrete logarithm problem (ECDLP), we prove that the CPP-CLAS scheme is existential unforgeability under adaptively chosen message attacks (EUF-CMAs). Performance and security analyses show that the CPP-CLAS scheme is more efficient and secure than other existing related schemes.