Sender anonymity in Location-based services (LBS) refers to hiding the identity of a mobile device user who sends requests to the LBS provider for services in her proximity (e.g. "find the nearest gas station etc."). The goal is to keep the requester's interest private even from attackers who (via hacking or subpoenas) gain access to the LBS request and to the locations of the mobile user and other nearby users at the time of request. In an LBS context, the best-studied privacy guarantee is known as "sender k-anonymity." We show that the state-of-the art solutions for sender k-anonymity defend only against the naive attackers who have no knowledge of the anonymization policy that is in use. We strengthen the privacy guarantee to defend against more realistic "policy-aware" attackers. We describe a polynomial algorithm to obtain an optimum anonymization policy. Our implementation and experiments show that the policy-aware sender k-anonymity has the potential for practical impact, being efficiently enforceable, with limited reduction in utility when compared to policy-unaware guarantees. Next we extend the policy-aware privacy guarantee to a class of attackers who knows historical user locations i.e. trajectory-aware. We call it the trajectory-aware policy-aware sender k-anonymity guarantee. We describe how this novel privacy guarantee is provided in an "offline" scenario, when a LBS provider logs the LBS requests sent by its users over a period of time and later wants to publish/share these logs. While these logs can be extremely valuable for advertising, data mining research and network management, we show they pose serious threat to anonymity of the LBS users. We describe a method to anonymize these LBS request logs and preserve trajectory-aware policy-aware sender k-anonymity in the offline scenario. We show that finding the optimum offline policy that provides trajectory-aware policy-aware k-anonymity is "NP-Hard." Hence, we describe a novel bounded approximation algorithm and empirically show the effectiveness of this approximation algorithm for anonymizing large sizes of data (up to 1 million users). [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.bibliotheek.ehb.be/en-US/products/dissertations/individuals.shtml.]