P3RN：基于道路网络的个性化隐私保护

# P3RN：基于道路网络的个性化隐私保护 ## 1. 引言 随着无线通信和移动定位技术的发展，基于位置的服务（LBS）得到了广泛应用，为用户带来了极大便利，但也增加了个人信息（如位置）泄露的风险。一般来说，LBS 中的隐私保护主要关注用户的三种信息：身份、位置和敏感信息。 ### 1.1 现有隐私保护方法 - **身份保护**：位置 k - 匿名模型是最常用的隐藏用户身份的方法。例如，在一个隐藏集合中，多个用户的位置用一个路段集合表示，使得攻击者无法区分集合内用户的身份。 - **位置保护**：基于位置 k - 匿名模型，位置隐藏是常用的方法，其主要思想是降低用户位置的空间和时间分辨率。在欧几里得空间中，精确位置通常扩展为矩形或圆形；在道路网络等受限空间中，精确位置通常发布为路段集合。 ### 1.2 敏感信息披露问题 大多数现有工作侧重于身份和位置保护，很少关注防止敏感信息披露。敏感信息可以通过位置语义和查询语义两种公开信息泄露。为了保护敏感信息，除了位置 k - 匿名模型，隐藏集合还需遵循 l - 多样性模型，但这两个模型不足以完全保护敏感信息。 ### 1.3 个性化同质性攻击 隐私需求是个性化的，一个查询是否敏感取决于用户的个性化隐私要求。当一个隐藏集合中的所有查询对某个用户来说都是敏感的，我们称这种攻击为个性化同质性攻击。 ### 1.4 本文工作 为了解决上述问题，本文提出了 (K, L, P) - 匿名模型和基于道路网络的个性化隐私保护隐藏算法 P3RN。具体贡献如下： - 提出 (K, L, P) - 匿名模型，旨在保护用户的身份、位置和敏感信息。 - 提出 P3RN 隐藏算法，支持用户的个性化隐私要求。 - 进行了一系列初步实验，验证了 P3RN 的效率和有效性。 ## 2. 相关工作 ### 2.1 敏感信息披露相关工作 - Hu 等人首先观察到匿名位置数据与参考数据集连接时敏感信息披露的问题，但仅遵循位置 k - 匿名模型。 - 位置 l - 多样性模型被引入，要求隐藏区域包含 k 个移动用户和 l 个地点，但未区分地点类型。后续工作对 l - 多样性的定义进行了细化，并将地点分为敏感和非敏感地点。 - 有工作指出使用查询语义的同质性攻击问题，并提出 p - 敏感模型和 PE - 树，但存在维护成本高、用户隐私要求相同、系统统一定义查询敏感性等缺点。 ### 2.2 道路网络匿名化方法 现有道路网络匿名化方法分为四类：基于树型索引的隐藏算法、基于图遍历的隐藏算法、基于混合区的隐藏算法和基于 PIR 的匿名化算法。基于图遍历的隐藏算法生成的隐藏集合反映了道路网络的特征，有助于降低 LBS 服务器的查询成本，是目前道路网络中最广泛使用的隐私保护方法。本文提出的 P3RN 算法与基于图遍历的方法一致。 ## 3. 预备知识 ### 3.1 基本定义 #### 3.1.1 类别 - 敏感性关系（CaSR） 采用集中式系统，包括移动用户、可信匿名代理（TAP）和不可信服务提供商。TAP 中存储类别 - 敏感性关系 CaSR，它是从查询类别关系到敏感性关系的多对一关系。通过 CaSR，每个查询被标记为一个敏感性。 CaSR 的定义如下： 设 D(CaSet) 和 D(SSet) 分别是查询类别和敏感性的域，则 CaSR = {(a, b)|a ∈ D(CaSet), b ∈ D(SSet), if (a1, b1), (a2, b2) ∈ CaSR, a1 = a2, then b1 = b2} 例如，CaSR = { (敏感位置导航, 绝密), (紧急呼叫, 更机密), (位置敏感计费, 机密), (信息娱乐服务, 较不机密), (购物指南, 非机密), (旅游指南, 非机密) }，其中 D(CaSet) = { 敏感位置导航, 紧急呼叫, 位置敏感计费, 信息娱乐服务, 购物指南, 旅游指南 }，D(SSet) = { 绝密, 更机密, 机密, 较不机密, 非机密 }。 CaSR 有两个属性： - 属性 1：对于任意两个查询 qi 和 qj，如果它们属于同一类别，则它们的敏感性相同。 - 属性 2：对于任意两个查询 qi 和 qj，如果它们的敏感性不同，则它们的类别不同。 #### 3.1.2 道路网络表示 将道路网络定义为无向图 G(V, E)，其中 V 是顶点集，包括交叉口和端点；E 是无向边集，表示两个顶点之间的道路路段。 #### 3.1.3 隐私配置文件 为了保护用户在道路网络上的个性化隐私，每个用户指定三种参数： - 匿名性要求 k：位置 k - 匿名模型中的匿名级别，用于保护用户身份。 -