结合差分隐私和PIR实现高效强隐私保护

### 结合差分隐私和PIR实现高效强隐私保护 在当前的k近邻（kNN）查询中，保障强位置隐私的可行技术之一是AHG算法。不过，AHG算法在处理大规模空间数据集时存在效率问题，因此提出了自适应查询计划（AQP）来解决这些问题。 #### 1. AHG算法概述 AHG是一种基于硬件的私有信息检索（PIR）算法，它利用查询计划来避免访问模式攻击。具体设置如下： - **数据存储**：位置服务提供商（LBS）将数据以顺序块的形式存储。对兴趣点（POIs）施加希尔伯特索引网格G，将其分组到各个单元格中。单元格按希尔伯特值排序，LBS将这些单元格及其POI计数存储在数据库DB1的多个PIR块中，同时将单个POI块分别存储在数据库DB2和DB3中。其中，DB1是DB2中POI的索引，DB2保存POI的实际位置（经纬度）和指向DB3的指针，DB3存储POI的尾部记录，如街道地址、电话号码和详细信息。 - **查询计划**：用户向连接到LBS的可信CPU发出kNN查询，使用固定查询计划QP = ((DB1, cnt1), (DB2, cnt2), (DB3, k))，确保每个查询从每个数据库中检索相同数量的块，与查询位置无关。具体步骤为：用户先从DB1获取cnt1个索引块，然后使用索引从DB2检索cnt2个包含POI坐标的块，定位k个最近的POI，最后向DB3发出查询，获取k个相应的块。为保证每个用户获得足够的块以得到准确答案，cnt1和cnt2是任何可能查询位置所需块数的上限。 #### 2. AHG算法的问题 AHG的固定查询计划使得每个用户接收准确回答所有可能查询所需的最大块数。但由于查询分布通常遵循POI的分布，绝大多数查询只需要相对较少的块，因此大多数用户会获得大量冗余块，这对LBS的处理成本和用户的响应时间都有负面影响，导致AHG在处理实际中常见的大型空间数据集时速度过慢。 #### 3. 自适应查询计划（AQP） 为解决AHG的问题，提出了AQP，它能为大多数查询提供准确的kNN集合，但可能会导致数据空间稀疏区域中预定义百分比（1 - α）的查询结果不准确。α值用于调整准确性和效率之间的权衡。 - **框架阶段**： 1. **查询阶段**：有固定周期（如一天），用户向LBS发出kNN查询，每个用户最多可发出qmax个私有kNN查询，并记录当前周期内每个查询的冗余块数量。 2. **查询计划重新计算阶段**：LBS以差分隐私的方式从用户获取冗余数据，计算冗余块的分布以及回答已发出查询所需的块数，最后为下一个查询阶段生成AQP，确保至少α百分比的查询能获得足够的PIR块以得到准确结果。 #### 4. 查询阶段 在查询阶段，每个用户u维护两个向量： - **Ru向量**：长度为cnt1 + 1，存储从DB1接收的冗余块数量。每个元素j表示用户u收到j个冗余块的查询次数，最后一个元素Ru[cnt1]表示块不足（可能结果不准确）的查询次数。 - **Su向量**：长度为cnt2 + 1，用于数据库DB2，功能与Ru类似。 以下是一个查询阶段的示例： 假设有20个POI（P1到P20）、一个6×6的网格和一个查询位置Q。所有单元格按希尔伯特值排序，存储在DB1中。每个DB1块最多容纳8个单元格，DB2每个块最多包含4个POI，按单元格的希尔伯特值排序，DB3存储POI的尾部信息。 设查询计划为((DB1, 2), (DB2, 4), (DB3, 2))，用户u在单元格c45从位置Q发出2NN查询。具体步骤如下： 1. **DB1查询**： - 计算c45的希尔伯特值H(4, 5) = 29，确定所需块为(29 + 1) / 8 + 1 = 4，c45的位置为(29 + 1) mod 8 = 6，指示安全CPU检索块B1,4。 - c45的值对为(17, 0)，表示该单元格中没有POI，继续查询下一个最接近Q的单元格c35，它属于已检索的块B1,4。 - c35包含一个POI，继续探索更多单元格。检索c44后，用户收集到2个POI，计算Q与检索单元格之间的最大可能距离maxdist，绘制以Q为中心、半径为maxdist的圆C1，忽略与圆C1无公共区域的单元格。但由于查询计划限制，用户从DB1获取的块不足，更新DB1的冗余向量Ru[2] := Ru[2] + 1。 2. **DB2查询**： - 用户按Q与从DB1检索的每个单元格之间的最小距离升序请求DB2中POI的坐标。例如，从c35获得(17, 1)，计算(17 + 1) / 4 + 1 = 5，(17 + 1) mod 4 = 2，确定POI在DB2的第5个块的第2个位置，请求B2,5。 - 每次检索POI的坐标时，更新当前的最佳2NN，并在当前2NN的距离小于Q与任何其他单元格之间的最小距离时进一步修剪搜索空间。最终用户收到3个块B2,1、B2,4和B2,5，但查询计划要求检索4个块，因此发送随机请求，再检索一个块，并更新DB2的冗余块向量Su[1] := Su[1] + 1。 3. **DB3查询**：用户跟随P9和P12的指针，从DB3检索块B3,2和B3,6以获取尾部信息。 #### 5. 重新计算阶段 在重新计算阶段，LBS聚合所有在线活跃用户的冗余向量。以DB1为例，具体步骤如下： - **用户设置**：每个活跃用户指定信任不与LBS勾结的用户百分比ℓ，该参数调整差分隐私机制添加的噪声规模。用户注册服务时，向LBS发送用于计算成对密钥的自签名Diffie - Hellman（DH）组件和用于身份验证的证书。 - **密钥计算**：重新计算开始时，LBS将自签名DH组件和证书分发给所有活跃用户，每个用户使用DH组件计算与其他用户共享的成对密钥。 - **数据处理**：每个用户u对Ru进行计算，然后将Ru的噪声加密版本ˆRu发送给LBS。LBS收集所有活跃用户的ˆRu后，得出聚合统计的差分隐私向量ˆR，并使用它生成新的AQP。具体计算过程如下： - 设n为活跃用户数，Ku,w为用户u和w共享的成对密钥，r1和r2为LBS发布的两个随机数，Ku为用户u与LBS之间的对称密钥。对于Ru的每个元素Ru[v]，用户u花费隐私预算λ = ϵ/(4 · qmax)，从伽马分布中抽取两个噪声值，计算ˆRu[v] = Ru[v] + Gu,1(n · ℓ, λ) - Gu,2(n