A new type of service, known as a Location Based Service (LBS), is emerging that incorporates users' location information, and many of these LBSs operate over the Internet. However, the potential misuse of this location information is a serious concern. Therefore, the main goal of this thesis is to develop techniques, which increase users' security and privacy, for use with these LBSs. The �rst technique that we propose is a three-party protocol that is used to mutually identify and authenticate users, LBSs, and a trusted middleware infrastructure that is responsible for managing the users' identity and location information. This protocol enables users to simultaneously identify and authenticate themselves to the infrastructure using real identities, and to the LBSs using pseudonyms. This protocol can be subsequently used to securely exchange messages containing location information. The second technique that we propose is an access control model that enables users to create permissions that specify which users and LBSs are entitled to obtain location information about which other users, under what circumstances the location information is released to the users and LBSs, and the accuracy of any location information that is released to the users and LBSs. The third technique that we propose is a blurring algorithm that performs spatial blurring on users' location information. It does not perform temporal blurring, because this reduces an LBS's ability to �offer a useful service. Instead, our blurring algorithm introduces a new parameter that speci�es the frequency with which location information is released for a particular user. This frequency parameter is a function of the size of the blurred location. These three techniques can be used as part of an overall solution for providing users with increased security while using LBSs that operate over the Internet.