By the technology developments and especially advent of smart phones with location sensors, location-based services become more popular everyday. The main attribute of these services is using user’s location information and supplying response based on location information. These services are so attractive because they are correlated to user’s real life, but they can also be threatening in case of misuse, thus privacy and security is an important issue in these services. There are many proposed methods to achieve this goal and the most important aspect of all methods is that the information send and reveal to whom and as much as needed for the service. Spatial and temporal cloaking, adding noise and trusted anonymizer server are some of most known methods, but none of them achieve this goal completely and they have some disadvantages either. In this thesis after a survey on previous methods, we propose a novel method based on fuzzy clustering and Bayesian theorem to improve clustering precision and it has been shown that this algorithm could deal with noisy datasets and clustered records with low certainty and thus it helps us to users location information more accurately even with added noise and we could extract users common seen places and thus determine user and his pattern. By this method we show that previous methods could not be trusted and especially if an invader has access to trusted server, he could achieve so many information about users even if they use pseudonym and thus trusted server is untrustable either. Then we propose a method based on separating queries from each others and users and we use ticket instead of ID for users. In this method we use cryptographic and hashing table to distribute queries and responses irregularly and thus the correlation between continuous queries will be eliminated and thus it is impossible for the intruder to determine users based on a sequence of queries. Proposet methods has been tested on some datasets such as MSR location dataset and experimental results show significant improvements in both methods. Keywords: Anonymizer, Trusted Server, Location-based social networks, Privacy, Pseudonym
