As vehicular communications bring the promise of improved road safety and optimized road traffic through cooperative systems applications, it becomes a prerequisite to make vehicular communications secure for the successful deployment of vehicular ad hoc networks. In this paper, we propose an efficient authentication protocol with anonymous public key certificates for secure vehicular communications. The proposed protocol follows a system model to issue on-the-fly anonymous public key certificates to vehicles by road-side units. In order to design an efficient authentication protocol, we consider a key-insulated signature scheme for certifying anonymous public keys of vehicles to the system model. We demonstrate experimental results to confirm that the proposed protocol has better performance than other protocols based on group signature schemes.