Authentication of vehicular safety messages poses a challenge in a high density road-traffic scenario as the verification time for gathered messages gets longer than the average inter-arrival time. This may expose a vehicular network entity to several different security attacks. The existing solutions have addressed the issue either by randomizing the verification candidates, or by using aggregated signature verification schemes, both of which have short-comings in terms of applicability in vehicular communications. The authors propose a novel solution to the vehicular message authentication in dense traffic conditions by introducing a prioritized verification strategy. Based on the relevance of physical parameters of neighboring vehicles, received safety messages are assigned with different priority scores at the verifying entity.