Sphinx: Certificateless Conditional Privacy-Preserving Authentication With Secure Transmission for VANETs

Conditional privacy-preserving authentication (CPPA) has been widely studied to ensure authentication, anonymity, and traceability in vehicle ad hoc networks (VANETs). Among CPPA schemes, certificateless CPPA (CL-CPPA) offers natural advantages for VANETs by avoiding the complex certificate management of PKI-based solutions and the key escrow problem of identity-based systems. However, many existing CL-CPPA schemes overlook secure message communication. When confidentiality is required, they often rely on additional encryption, which adds communication overhead comparable to that of certificate transmission in PKI-based solutions. Anamorphic signatures (proposed at CRYPTO'23) can be adopted to address this issue by embedding sensitive messages within signatures, which eliminates the need for separate encryption. However, existing anamorphic signature schemes are symmetric, requiring extensive key agreements between two entities, which is impractical for the dynamic nature of VANETs. In this paper, we introduce a new cryptographic primitive, asymmetric anamorphic signatures (AAS), which enables secure message sharing in a public-key setting, thus eliminating the need for complex key agreements. We also provide a concrete construction of AAS based on a variant of the Hohenberger-Waters signature scheme. By integrating AAS with CL-CPPA, we propose <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Sphinx</i>, a scheme that ensures authentication, anonymity, traceability, and confidentiality without the overhead of additional secure transmissions or complex key agreements. Our security proofs and performance evaluations demonstrate the practicality and efficiency of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Sphinx</i>, particularly its advantage in reducing communication overhead.