Abstract
Pseudonym Self-Generation (PSG) is essential for Conditional Anonymous Authentication (CAA) in Vehicular Ad-hoc Networks (VANETs), enabling vehicles to autonomously create communication identities without centralized control. However, existing self-generation schemes face two problems: efficiently revoking malicious vehicles remains difficult, and hardware-independent solutions additionally struggle to verify the legitimacy of pseudonyms. To overcome these issues, we propose an efficient Revocable CAA scheme with Verifiable Self-generated Pseudonyms for VANETs (<inline-formula> <tex-math notation="LaTeX">$\mathsf {RCAA_{VSP}}$ </tex-math></inline-formula>). First, a Traceable Chameleon Hash (TCH) function is designed to implicit membership through TCH collision, enforcing verifiable and unlinkable pseudonym generation. And then a multi-parameter authentication mechanism leveraging dynamic accumulators, which achieves <inline-formula> <tex-math notation="LaTeX">$O(1)$ </tex-math></inline-formula>-complexity revocation via domain membership polynomial updates without system-wide reconfiguration. Formal security analysis demonstrates the semantic security of our proposed scheme under the random oracle model, with proven resilience against common attacks. Experimental evaluations demonstrate that <inline-formula> <tex-math notation="LaTeX">$\mathsf {RCAA_{VSP}}$ </tex-math></inline-formula> achieves a 76% relative improvement in pseudonym generation efficiency, while maintaining the overhead of anonymous authentication and malicious vehicle revocation at ms-level, providing a lightweight solution for secure VANET communication.