Abstract: LBS privacy protection schemes based on centralized and distributed architecture have their own characteristics. On this basis, this paper designs a hybrid privacy protection architecture with both advantages and proposes a grid-based LBS privacy protection scheme. In this scheme, random offset parameters are regularly updated to users and LBS servers through parameter generator, by combining K-anonymity and random deviation, anonymous areas are generated in the central server, which not only ensures security, but also avoids potential security risks of traditional anonymous central servers. At the same time, grid coordinates are used to represent the anonymous region in the query result filtering process, which achieves efficient result matching and significantly reduces the computation cost of the central server. Compared with the existing scheme, this scheme also has more advantages in communication overhead. Security analysis and experiments show that the scheme can effectively protect users’ privacy and reduce the cost of the central server obviously.

Key words: location privacy protection, hybrid structure, grid technology, K-anonymity, random deviation

摘要： 基于中心式和分布式结构的LBS隐私保护方案的特点，设计了一种混合式隐私保护结构以兼具两者优势，并在该结构下提出了一种基于网格的LBS隐私保护方案。该方案使用参数生成器定期向用户及LBS服务器更新偏移参数，通过结合K-匿名和随机偏移技术，在中心服务器生成匿名区域。在保证安全性的同时，避免了传统匿名中心服务器存在的安全隐患。同时，在查询结果的筛选过程中，采用网格化坐标对匿名区域进行表示，实现了高效的结果匹配，显著降低了中心服务器的计算开销。较之已有方案，该方案在通信开销方面亦具有较大优势。

关键词: 位置隐私保护, 混合式结构, 网格化技术, K-匿名, 随机偏移