Abstract: According to the identity privacy exposure problem of location-based service, an identity attack algorithm based on bipartite graph is proposed. The basic idea is to build a bipartite graph between mobile users’ identity and their pseudonyms, and then use Kuhn -Munkres algorithm to find the best perfect match, finally determine the user’s identity to complete the attack. The effectiveness of the proposed algorithm is verified by experiment, and also the impact of the privacy protection mechanism, the privacy exposure rate of the location-based service, and pseudonyms lifetime on the algorithm is analysed.

Key words: location-based services, privacy exposure, bipartite graph, perfect match

摘要： 针对位置服务中的身份隐私泄露问题，提出了一种基于二分图的身份推理攻击算法。其基本思想是构建移动用户真实身份和假名间的有权二分图，运用Kuhn-Munkres算法找到其最佳完美匹配，确定用户的真实身份完成攻击。通过实验验证了该算法的有效性，并分析了隐私保护机制、位置服务隐私泄露率和假名生存期等因素对算法的影响。

关键词: 位置服务, 隐私泄露, 二分图, 完美匹配