VLDB'22：基于位置的高效安全可验证Skyline查询处理方法 - 网安 - 专业的网络安全产业、社区、知识平台

在云服务器上，针对加密数据进行大规模Skyline查询是一项重要挑战。由于密文计算的开销，其查询效率严重影响应用落地。此外，由于云服务器上的各种资源是不可信的甚至是带有恶意性的，所以保证数据安全性和结果可靠性也是亟待解决的主要问题。当前，很少的工作可以同时保证查询效率、数据机密性和结果可靠性。为此，该论文研究了支持隐私保护和可验证的位置服务Skyline查询（Secure and Verifiable Location-based Skyline Queries, SVLSQ）方法。该方法保护了数据集、查询点、结果和访问模式的隐私。同时，它可以验证Skyline结果的正确性和完整性，并有效地降低了验证对象的存储开销。性能评估的实验结果表明，SVLSQ在查询方面比现有方法提升了至少3个数量级，在验证方面也是非常高效的。

该成果“Efficient Secure and Verifiable Location-Based Skyline Queries over Encrypted Data”已被国际顶级会议VLDB 2022录用。VLDB是数据库领域CCF A类国际会议。

论文链接：
https://dl.acm.org/doi/abs/10.14778/3538598.3538605

背景与动机

本文研究了基于静态数据集（如，餐馆、酒店、停车场等）上可验证位置服务Skyline查询（Secure and Verifiable Location-based Skyline Queries, SVLSQ）的问题。如图1所示，是关于如何选择合适酒店的例子，其中P= {P₁, ..., P₆ }表示具有位置和价格的二维数据集，q是一个带有用户位置的查询。如果采用Skyline查询来为具有不同偏好的游客提前过滤酒店，那么q的真实Skyline结果{P₃ , P₄}。然而，由于商业因素，云服务器可能会返回被篡改的结果，如{P₃ , P₂ , P’}，例如，P₂是赞助该云计算平台的酒店，P’是一个伪造的且消费价格昂贵的酒店，以此来衬托并诱导游客选择酒店P₂。很明显，用户无法验证结果的可靠性。因此，SVLSQ提供了一种验证机制，从以下两个方面保证结果的真实性：?）正确性，即没有被篡改的结果（如P₂ , P’）；?）完整性，即没有被丢弃的结果（如P₄）。此外，如果没有隐私保证，数据集P、查询q和结果R等内容可能会被泄露给云服务器。为此，SVLSQ还旨在保护四个被广泛采用的隐私需求：?）数据隐私：数据集P；??）结果隐私：查询结果R；??）查询隐私：查询q；以及??）访问模式隐私：在P中的结果位置。

图1 Skyline查询处理示例

通过以上分析，本文的目标是提出基于静态或不经常更新的数据集（如酒店和停车场）上的可验证Skyline查询，以保证上述的隐私要求和查询结果的可靠性。然而，有几个关键的区别使得现有的技术无法适用于SVLSQ。首先，大多数现有的安全Skyline查询技术不能为客户提供结果验证。第二，大多数现有的R-tree索引的变体（例如Merkle R-tree）和它们的查询方法不能同时保证数据集、结果、查询和访问模式的隐私。第三，一种简单的方法是直接建立加密的R-tree索引。然而，这种方法不能保持查询的不可链接性，即云服务器可以跟踪两个查询的访问路径，以确定它们是否来自同一个查询。此外，这种不成熟的方法也无法保证在结果验证阶段的隐私泄露问题。

为了支持SVLSQ，有两个关键的技术挑战需要解决。

1) 如何为安全Skyline查询设计可验证数据结构 (Authenticated Data Structure, ADS)，同时保证数据的机密性和结果的可靠性？为此，本文首先提出了一种统一的索引结构，称为半盲化R-tree (Semi-blind R-tree, SR-tree)，以保持查询不可链接性。由于半盲化结构，P中结果的位置对云服务器是隐藏的。然后，根据SR-tree，使用Paillier、ORE加密算法和hash函数构建了安全可验证的R-tree（SVR-tree）索引。之后，本文提出了基于SVR-tree的Skyline搜索算法BVLSQ。然而，在BVLSQ中，过多的支配操作会影响查询效率，并且验证对象（VO）的体积过大。此外，尽管ORE算法保护了数据的内容（在VO中），但某些原始数据的顺序信息会泄露给客户端。为此，引出了本文的第二个挑战。

2）如何进一步加快效率、优化通信带宽、增强数据安全性？据观察，点的支配关系可以由数据所有者预先计算，从而可以进一步减少查询和验证时间。为了减少ORE密文带来的通信负担，本文设计了新颖的叶子结点结构，该结构在查询和验证过程中考虑了数据的机密性。总的来说，以SR-tree的半盲化思想为基石，本文提出了使用Paillier加密算法和哈希函数的安全可验证R-tree（SVSR-tree），它存储了加密的数据对象和验证信息（而不是加密数据点本身），并提出了对应Skyline查询协议。

设计与实现

本文采用了抗共谋的两个云服务器，设计了如图2所示的系统模型。它由以下四种实体类型组成：

数据所有者 (DO)：作为拥有数据集P的可信实体，DO生成Paillier密码系统的密钥<pk,sk>和散列函数???ℎ(·)，然后根据数据集P构建安全且可验证的索引?和附加的加密信息???。DO分别将??、?发送到DSP，并将<pk,sk>、???发送到DAP。在成功审核请求者的注册信息后，DO为其分配??和???ℎ(·)。
查询请求者 (QR)：授权客户端向DSP发送加密查询q。在收到来自DSP和DAP的查询结果和验证对象（即1,VO₁>和2,VO₂>）后，客户端进一步计算Skyline结果并检查其可靠性。
云服务器：数据服务提供商(DSP)是一台云服务器，在收到来自QR的查询请求时，与数据协助提供商(DAP)合作，根据索引?和加密查询q，处理安全且可验证的Skyline查询。查询完成后，DSP和DAP分别返回1,VO₁>和2,VO₂>。

图2 系统模型

SVLSQ的基本思路概述如下：

数据拥有者将同一父结点的叶结点构成结点桶（Node Bucket, NB）的集合。例如，如图3所示，结点?₇有索引对象?₃、?₄和?₅，其叶结点分别是?₃、?₄和?₅。因此，?₃、?₄和?₅被构造成结点桶NB，其对应的索引对象也被称为盲对象。对于每个盲对象，数据有者设置了加密向量??，如果盲对象对应于??中的第?结点，则??[?]为Paillier加密值1并且其余维度为Paillier加密值0。因此，在半盲化结构中，以加密向量??和结点桶??作为输入，通过函数B(·)可以计算对应加密叶子结点。数据所有者将除加密向量??之外的SR-tree上传到云服务器DSP，并将加密向量集合??s作为附加加密信息上传到DAP。由于Paillier的概率特性，相同叶结点的密文是不同的。因此，每个结点都是秘密地从??“读取”的，云服务器无法知道它在数据集中的确切位置。

图3 SR-tree示例

为了提供结果验证服务，本文利用SR-tree有效地组织数据点及验证信息，并构建了SVSR-tree。在叶结点中，数据对象除了保存加密的Skyline数据点外，还记录了一些辅助验证信息，如Skyline Scope、近似多边形、摘要及签名值，所有这些验证信息都是被Paillier算法加密。在非叶子结点中，索引对象记录了加密的最小外接矩形（Minimum Bounding Rectangle, MBR）和摘要值。然后，数据拥有者生成签名???(Hr)，其中Hr表示为根哈希。基于SVSR-tree，本文利用分支定界法构建了查询协议，并返回结果和验证对象。最后，客户端基于验证对象来验证结果的正确性和完整性。

实验评估

在实验中，研究通过与完全安全Skyline协议（FSSP）和基础安全Skyline协议（BSSP）进行比较，评估了BVLSQ协议和SVLSQ协议的查询性能，同时也评估了它们的结果验证性能。

图4展示了通过改变数据点个数n在不同数据集上的查询时间开销(s)。其中，BVLSQ和SVLSQ比BSSP更安全。此外，与FSSP协议类似，BVLSQ和SVLSQ协议可以保护访问模式的隐私。然而，BVLSQ和SVLSQ协议比FSSP更加高效。这是因为BVLSQ采用了SVR-tree索引，通过安全剪枝操作减少了不必要的计算开销。此外，SVLSQ的查询效率明显又高于BVLSQ，原因是通过预先计算数据集中点的支配关系，计算开销可以进一步减少。同时，据观察，随着?的增加，SVLSQ非常适用于大数据集。

图5展示了通过改变非空间维度d*在不同数据集上的查询开销(s)。据观察，SVLSQ的查询性能明显优于BSSP和BVLSQ。同时，随着d*的增加，SVLSQ和BVLSQ之间的效率差距变得更大。这是因为SVLSQ的SVSR-tree索引仅需要构建在二维空间属性上，其查询时搜索的维度更少。

图4 参数n的查询影响（d*=2）

图5 参数d*的查询影响（n=1000）

图6和7表明SVLSQ比BVLSQ需要更少的内存开销，因为它只需要为结果验证提供的更少信息。具体来说，SVLSQ的查询并不涉及非空间属性，其验证对象树??????仅包含二维的验证对象信息。对于BVLSQ的??????，它包括?维的验证对象信息。同时，SVLSQ 比BVLSQ需要更少的验证时间。正如预期的那样，它们中的??????的内存开销都随着?的数量增加而增加，并且它们的验证时间也大致随着?的增加而增加。从图6中，观察到当?*增长时，BVLSQ和SVLSQ的验证时间都大致呈指数增长。BVLSQ中??????的内存开销随着维度?*的增加呈近似线性增加。对于SVLSQ而言，它的??????内存开销也大致随着?*的增加而增加。其原因是随着?∗的增加，更多覆盖查询点的对象及其相关验证信息被插入到??????中，这会占用更多的内存空间。

图6 参数n的验证影响（d*=2）

图7 参数d*的验证影响（n=1000）