The invention is applicable for use in conjunction with a system for connected vehicle communications in which each vehicle in the system is issued a limited number of unique pseudonym certificates that are used by the vehicle to establish trust in messages sent by the vehicle by signing each message with a pseudonym certificate. A method is set forth for selecting a pseudonym certificate for use, from among the vehicle's pseudonym certificates, so as to protect the privacy of the vehicle's activity against attacks by eavesdroppers, including the steps of: tracking and storing vehicle location data; computing, from inputs that include the vehicle location data, the vehicle's relative achievable anonymity in particular geographical regions; prioritizing the pseudonym certificates; and selecting a pseudonym certificate for use from among the pseudonym certificates having a priority that is determined by the relative achievable anonymity for the geographical region in which the certificate is to be used. The method includes authenticating a safety message using the selected pseudonym certificate, and transmitting the authenticated message.