Abstract: Location k-anonymity becomes a research focus in the privacy-preserving field of location-based service recently．Typical spatial cloaking algorithms require a centralized trusted anonymity server which could be the system bottleneck and single point of attacks,while the existing spatial cloaking algorithms in P2P (Peer to Peer) mode suffer from several attack models．A spatial cloaking algorithm based on grid expansion in P2P mode was proposed to solve this problem．It divides the space into grids and computes cloaking region by keeping trying to double the grid’s width until user’s privacy requirement is satisfied．Meanwhile the intermediate result is shared and cached with other peers during the running process of the algorithm．The experimental results show that the proposed algorithm reduces the consumption of network bandwidth and time cost of spatial cloaking．Moreover,it is free from center-of-cloak attack and more resistant to sample query attack in comparison with the existing algorithms.

Key words: Location-based service,Location privacy,k-Anonymity,P2P