In this paper, we introduce an anonymous batch authenticated and key agreement (ABAKA) scheme to authenticate multiple requests sent from different vehicles and establish different session keys for different vehicles at the same time. In vehicular ad hoc networks (VANETs), the speed of a vehicle is changed from 10 to 40 m/s (36-144 km/h); therefore, the need for efficient authentication is inevitable. Compared with the current key agreement scheme, ABAKA can efficiently authenticate multiple requests by one verification operation and negotiate a session key with each vehicle by one broadcast message. Elliptic curve cryptography is adopted to reduce the verification delay and transmission overhead. The security of ABAKA is based on the elliptic curve discrete logarithm problem, which is an unsolved NP-complete problem. To deal with the invalid request problem, which may cause the batch verification fail, a detection algorithm has been proposed. Moreover, we demonstrate the efficiency merits of ABAKA through performance evaluations in terms of verification delay, transmission overhead, and cost for rebatch verifications, respectively. Simulation results show that both the message delay and message loss rate of ABAKA are less than that of the existing elliptic curve digital signature algorithm (ECDSA)-based scheme.
