Because of the large number of deaths, severe injuries and huge financial loss due to auto accidents and poor traffic management, road safety and traffic management have become very important areas of interest among research community. As a result, Vehicular Ad-hoc Network (VANET) becomes a promising technology to improve road safety and quality of traffic management. The VANET includes vehicles with On-Board Units (OBUs), Road Side Units (RSUs) and other entities such as servers connected through RSUs. Moreover, Vehicle-to-Vehicle and Vehicle-to-Infrastructure communications are used to exchange required data and information with neighboring vehicles and other infrastructure entities. Although VANET has attracted much attention in the past few years, security and privacy did not get enough consideration until recently. Security and privacy of VANETs must be taken care of before introducing VANETs to the general public. Security requirements such as authentication, integrity, non-repudiation and authorization have to be provided while simultaneously achieving user privacy in terms of anonymity and unlinkability. However, none of these mechanisms should adversely affect the quality of services in terms of level of safety and real-time processing. To achieve required security services while preserving anonymity and unlinkability, three protocols are proposed for VANETs: 1. Efficient and Scalable Anonymous Authentication Protocol, which provides required security and privacy services, 2. Synchronized Pseudonym Changing Protocol to effectively change pseudonyms to enhance unlinkability in safety applications, and 3. Anonymous Online Service Access Protocol to achieve anonymity and unlinkability in online service access in VANETs. Collectively, all the required security services such as authentication, non-repudiation, integrity are achieved in a very efficient and scalable manner. When comparing with existing security protocols, this set of protocols produces 20%-40% lower computational and communication overhead. Furthermore, a highly efficient certificate distribution mechanism which does not rely on unreliable RSU, is achieved and inefficient Certificate Revocation Lists are avoided in certificate revocation. More importantly, simulation and analytical evaluations show that these protocols give 40% higher level of unlinkability for both safety and online applications. It further proves the feasibility of these protocols in different VANET scenarios with reasonable overhead and minimum affect on vehicular safety. [The dissertation citations contained here are published with the permission of ProQuest LLC. Further reproduction is prohibited without permission. Copies of dissertations may be obtained by Telephone (800) 1-800-521-0600. Web page: http://www.proquest.com/en-US/products/dissertations/individuals.shtml.]