In this paper, we propose an efficient authentication protocol based on certificateless signature scheme, which does not need anyinfrastructure to deal with certification of public keys, among the vehicles in Vehicular Ad-hoc Networks. Moreover, due to the characteristicsof VANET nodes (i.e., vehicles) that is fast and movement, the proposed protocol introduces the concept of interval signing key to overcome efficiently the problem of certificate revocation in traditional Public Key Infrastructure(PKI).