Privacy in Vehicular Ad Hoc Networks (VANET) is fundamental because the user's safety may be threatened by the identity and the real‐time spatiotemporal data exchanged on the network. This issue is commonly addressed by the use of certified temporal pseudonyms and their updating strategies to ensure the user's unlinkability and anonymity. IEEE 1609.2 Standard specified the process of certifying pseudonym along with certificates structure. However, the communication procedure between the certifying authority and the requesting vehicle was not defined. In this paper, a new privacy‐preserving solution for pseudonym on‐road on‐demand refilling is proposed where the vehicle anonymously authenticates itself to the regional authority subsidiary of the central trusted authority to request a new pseudonyms pool. The authentication method has two phases, the first one uses anonymous tickets, and the second one is a challenge‐based authentication. The anonymous tickets are certificates that do not include the identity of the user. Instead, it contains a reference number and the certifying authority signature. The challenge authentication is identity‐less to preserve the privacy, yet it is used to prevent the misuse of tickets and the impersonation of its owner. Our proposed scheme is analyzed by the use of Burrows, Abadi and Needham (BAN) logic to demonstrate its correctness. It is also specified and checked by using the Security Protocol ANimator (SPAN) and the Automated Validation of Internet Security Protocols and Applications (AVISPA) tools. The logical demonstration proved that this privacy‐preserving authentication is assured. The SPAN and AVISPA tools illustrated that it is resilient to security attacks.