We propose PUCA – a scheme that provides full anonymity for honest users, even against colluding backend providers. The scheme uses anonymous credentials for authentication with the backend, while leaving the communication among vehicles and with road side units unchanged and in compliance with existing standards. For removal of misbehaving vehicles from the system, we leverage a privacy-friendly revocation mechanism, that does not require resolution of pseudonyms. With our scheme, we demonstrate that strong and verifiable privacy protection in vehicular networks can be achieved, while fulfilling common security requirements, such as sybil-resistance and revocation.