Abstract: Vehicular ad hoc networks (VANETs) is a large network that runs according to a special communication protocol to achieve wireless communication and information exchange among vehicles and roadside infrastructures, pedestrian, Internet and so on. With the development of cloud computing, more and more cloud services for VANETs will emerge. However, the services are usually provided by different servers. Thus, vehicle users have to register different servers and remember a lot of usernames and passwords. Aimed to the goal that a user can do mutual authentication with all servers after hisher one-time registration, the multi-server architecture authentication protocols have been proposed and applied in many areas, but no one focuses on VANETs. The instantaneity of communication in VAENTs poses a new challenge on the multi-server architecture authentication protocol. The existing multi-server architecture authentication protocols use the complex bilinear pairing operations, which cannot meet the strict requirements of VANETs on authentication and communication costs. In this paper, a new efficient anonymous mutual authentication and key agreement protocol for the multi-server environment of VANETs is proposed. The proposed protocol decreases the complexity of protocol by using elliptic curve cryptosystem (ECC) to construct a simple authentication way, and provides the function of random anonymity to protect the privacy of vehicle. The security of the proposed protocol is proved in the random oracle model. Performance analysis shows that compared with the most recent mutual authentication protocols, our protocol decreases the computation and communication cost at least 61% and 62% in the mutual authentication and key agreement phase, and can better meet the computation and communication cost requirements of VANETs.