© 2018 IEEE. Vehicular ad-hoc networks (VANETs) are under active development, thanks in part to recent advances in wireless communication and networking technologies. The most fundamental part in VANETs is to enable message authentications between vehicles and roadside units. Message authentication using proxy vehicles has been proposed to reduce the computational overhead of roadside units significantly. In this message authentication scheme, proxy vehicles that verify multiple messages at the same time improve roadside units' efficiency. In this paper, first we show that the only proxy-based authentication scheme (PBAS) presented for this goal by Liu et al. cannot guarantee message authenticity, and also it is not resistant against impersonation and modification attacks and false acceptance of batched invalid signatures. Next, we propose a new identity-based message authentication scheme using proxy vehicles (ID-MAP). Then, to guarantee that it can satisfy the message authentication requirement, existential unforgeability of underlying signature against adaptively chosen-message and identity attack is proved under elliptic curve discrete logarithm problem in the random oracle model. It should be highlighted that ID-MAP not only is more efficient than PBAS since it is pairing-free and identity-based, and also it does not use map-to-point hash functions, but also it satisfies security and privacy requirements of VANETs. Furthermore, analysis shows that the required time to verify 3000 messages in ID-MAP is reduced by 76% compared to that of PBAS.