tl;dr: strategies to execute batch verification and when it effectively turns worse than multiple standard ones.
Paper: ICPS 2025 or personal pdf.
Sujash Naskar, Carlo Brunetta, Gerhard Hancke, Tingting Zhang, Mikael Gidlund
Vehicular Ad-Hoc Networks (VANETs) enable vehicles to share critical data for safety and traffic management. To improve efficiency, batch verification is used to authenticate multiple vehicle-to-vehicle (V2V) messages at once.
However, proposed solutions avoid error-prone environments with faulty signatures because of the higher analytical complexity, thus considering only error-free scenarios. This paper considers the error-prone scenario and proposes a novel strategy that allows optimal aggregation computations and reuse of such pre-computations to minimize the computational cost of identifying the faulty signature in a batch.
Our analysis shows that batch verification outperforms standard methods when the error rate is below 40%, with advantages up to 63% in typical scenarios. We provide guidelines for when batch verification is more efficient and suggest improvements to further optimize its performance in VANETs, offering a practical solution for real-world applications.