Determining whether the number of vehicles reporting an event is above a threshold is an important mechanism for VANETs, because many applications rely on a threshold number of notifications to reach agreement among vehicles, to determine the validity of an event, or to prevent the abuse of emergency alarms. We present the first efficient and secure threshold-based event validation protocol for VANETs. Quite counter-intuitively, we found that the z-smallest approach offers the best tradeoff between security and efficiency since other approaches perform better for probabilistic counting. Analysis and simulation shows that our protocol provides > 99% accuracy despite the presence of attackers, collection and distribution of alerts in less than 1 second, and negligible impact on network performance.