This paper investigates the critical privacy implications of short-time certificates to vehicular ad hoc networks (VANETs). A short-time certificate-based privacy protection scheme, STCP2, is proposed to address such privacy implications. STCP2 features a progressive roadside unit (RSU) deployment algorithm to optimize RSU deployment with cost and application constraints, while providing a minimal privacy assurance to vehicular nodes against the power abuse of VANET authorities. Besides, secure and privacy-preserving pseudonym change procedures enable each node to protect its privacy against both external and internal observers. As such, STCP2 properly protects the privacy of nodes with short-time certificates, as shown by theoretical analysis and simulations.