Aimed at improving the security and efficiency of anonymous authentication in vehicular ad hoc network (VANET), a certificateless batch anonymous authentication scheme without bilinear pairings is put forward. By coordinating Trust Authority (TA) and vehicles to generate the public/private key pairs and pseudonyms, the system security is freed from dependency on tamperproof devices. Through comprehensive analyses, this scheme is proved not only to be able to realize such security properties as authentication, anonymity, traceability, unforgeability, forward or backward security, etc., but also able to resist Type I and Type II attacks in the random oracle model. Moreover, this scheme effectively reduces system storage load by means of certificateless authentication, and the authentication efficiency can also be increased by realizing batch authentication based on pairing-free calculation. Accordingly, the scheme is proved to be significant in theory and valuable in application in the Internet of Things or embedded environment with limited resources.