基于加密数据的安全多方Skyline查询协议

在云服务器上，针对密文数据进行大规模Skyline查询是一项现有挑战。由于密文计算，现有的安全Skyline查询方案会产生大量的通信和计算成本。因此，本文利用加法同态和代理重加密来加密数据集，并基于该加密数据集进行Skyline查询计算。然而，基于该密码系统的安全计算将进一步降低查询效率。因此，为了提高加密数据的计算效率，本研究重新设计了两个轻量级的安全比较协议。同时，提出了“blind-reading”的有效方法来安全地获取Skyline点。接着，通过设计的隐私矩阵来减少数据集的规模，从而在不泄露隐私的情况下显著降低计算成本。然后，通过集成轻量级安全比较协议、“blind-reading”和隐私矩阵技术来构建安全Skyline查询协议。最后，其性能评估表明，与现有技术相比，所提出的方法显著提高了效率（至少快了4.5倍），并且在大型数据集下具有良好的可扩展性。

该成果“Efficient and Privacy-Preserving Multi-Party Skyline Queries over Encrypted Data”被CCF A类国际期刊IEEE Transactions on Information Forensics and Security录用，该期刊每月出版一期，平均每期发表论文15篇左右。

• 论文原文：https://ieeexplore.ieee.org/abstract/document/9526638

背景与动机

本文研究安全Skyline查询的问题，它是各种场景的主要查询类型和基本构建块，例如基于位置服务的系统、多目标决策等。例如，假设数据医疗机构出于隐私考虑，希望将其肝癌电子病历外包给公有云，并对数据进行加密以确保数据保密。令P表示具有属性ID、年龄、T-BIL（总胆红素）、ALB（白蛋白）等的肝癌数据集。为了便于说明，对具有两个属性的四个患者记录p₁，... ，p₄进行采样（如图1所示）。考虑一位医生正在治疗肝病患者q=(30,29)，并希望检索相似患者以增强个性化治疗。然而，由于不同用户的主观偏好，通常很难统一定义所有属性的权重来进行kNN查询并返回最近邻结果。例如，如果仅涉及T-BIL，则p₁是最近的，而如果仅涉及ALB，则p₂和p₄是最近的。为此，Skyline查询可以通过涉及所有可能的相对属性权重来获取所有可能的1NN记录，从而可以作为疾病诊断的过滤器。接下来，对于每个维度j，使用函数 将数据点映射到新空间。 如果一个元组t _i 不能被任何其他元组支配（即，t _i 至少在一个维度上优于t _j 并且在所有其他维度上都不其差），则该元组即为Skyline点之一。 因此，很容易将Skyline点识别为t ₁ 和t ₂ （即p ₁ 和p ₂ ）。 值得注意的是，在上面的例子中，保护隐私是必不可少的，它一般涉及四个方面： 1）数据隐私，即数据集P； 2）查询隐私，即查询q； 3）Skyline结果隐私，即结果R； 4）间接隐私，即支配关系（即支配点的位置）。

图1 Skyline查询处理示例

为了支持对加密数据的安全多方Skyline查询（Secure Multi-party Skyline Query，SMSQ），论文引入了代理重加密和部分同态加密技术来加密外包数据、查询和结果。但是，仍存在以下几个关键技术挑战亟待解决：

1. 如何提高安全支配协议的效率？为此，本文提出了轻量级安全整数比较协议。在此基础上，设计了轻量级安全向量比较协议来提高两点之间的比较效率，这是安全支配协议的核心。
2. 如何安全有效地获取Skyline点并将其从数据集中消除？为了不透露有关Skyline点的内容，提出了“blind-reading”的方法，它可以从数据集中安全地读取Skyine点。
3. 如何在不透露支配关系（间接隐私）的情况下减少安全支配协议的调用次数？也就是说，使得安全支配协议在每次迭代中都在更小的数据集上执行。一种简单的方法是直接消除数据集中由Skyline点支配的点，但这会导致间接隐私的泄漏。为了解决该问题，本文提出了名为“隐私矩阵”的有效方法，这是减少数据集规模的关键步骤，以便在不泄露任何隐私的情况下显着降低安全天际线查询处理的计算成本，同时保证了查询准确性。

设计与实现

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

1. 数据所有者 (DO)：设χ为DO的数量。DO _i使用带有Diffie-Hellman密钥PK的HRES密码系统对其数据集P _i进行本地加密，其中1 ≤ i ≤ χ。当每个数据所有者将加密数据集E _PK(P _i)上传到云端后，就会合并成新的加密数据集E _PK(P)。通过DSP和DAP的协作，加密数据集E _PK(P)可用于安全的天际线查询。
2. 查询请求者 (QR)：令o为QR的数量。具有一对密钥(pk _q,sk _q)的第q个授权客户端打算获取关于查询元组的Skyline结果集，其中1≤q≤ o。为了保护查询元组的隐私，客户端使用 DiffieHellman 密钥PK加密查询并将E _PK(q _q)发送到DSP。根据HRES密码系统的性质，DSP和 DAP不能单独解密E _PK(q _q)。
3. 云服务器：数据服务提供商（DSP），拥有一对密钥(pk _DSP,sk _DSP)，可以存储加密数据，其利用HRES的同态特性来计算密文，并提供 Skyline查询处理服务。此外，DSP可以将加密消息转化为DAP的密文，再DAP来进行解密。DAP是另一个云服务器，它拥有自己的一对密钥(pk _DAP,sk _DAP)并协助计算。即DAP使用PDec2算法来解密转化后的密文，并将中间消息返回给DSP，DSP继续处理安全Skyline查询。当协议完成时，DAP将加密结果返回给客户端。

图2 系统模型

SMSQ协议旨在针对加密数据来处理安全动态Skyline查询。其工作原理概述如下：

1. 首先，当接收到来自客户端的查询E _PK(q _q)时，DSP根据其需要将E _PK(P)映射到一个新空间；
2. 之后，DSP 在初始化阶段主要通过 SSED协议计算数据点和原点之间的欧几里德距离；
3. 接下来，提出了“blind-reading”的新方法，它支持对 Skyline元组的安全访问，而且能保证云服务器无法获得Skyline元组的内容，也无法知道哪些元组是Skyline点；
4. 在拥有skyline元组后，DSP通过安全支配协议得到它与其他元组的支配关系DR _m。如果直接解密DR _m，则可以直接消除支配元组，这是本文所提出基础安全Skyline查询协议（BMSQ）。显然，通过直接解密DR _m，支配元组的位置被泄露给了DSP。为此，研究进一步提出了随机Skyline搜索算法，它是SMSQ的一个关键组成部分。通过该算法，DSP可以进一步缩减数据集大小，并返回步骤3）获取下一个Skyline元组；
5. 一旦DSP得到所有的Skyline结果，云服务器通过REnc算法将它们转化为客户端可解密的密文。最后，将它们返回给客户端，并由用户进行解密。

实验评估

在实验中，研究通过与完全安全Skyline协议（FSSP）进行比较，评估了基础多方Skyline查询（BMSQ）协议和安全多方Skyline查询（SMSQ）协议的性能。

图3展示了通过改变n在不同数据集上的计算时间开销 (s)。虽然SMSQ比BMSQ更安全，但它的效率接近BMSQ。在相同的安全级别下，FSSP比SMSQ产生更多的计算开销。这是因为不断迭代，SMSQ的数据量不断减小，从而减少了密文计算的时间开销。此外，通过增加n，所有数据集的SMSQ的计算时间开销大致线性增加。请注意，NBA数据集上协议的时间开销很低，因为n的范围只有1000到2500。

图4展示了通过改变d在不同数据集上的计算时间开销(s)。从这些图中，观察到SMSQ比FSSP更有效率，因为在迭代过程中消除了被支配元组，减少了数据集大小。此外，SMSQ的计算时间开销随着d的增加大致呈线性上升。研究还观察到NBA数据集的计算时间成本高于在CORR数据集上运行的协议。这是因为NBA数据集比代码生成的CORR数据集有着更弱的相关性。

图3 参数n的影响（d=2）

图4 参数d的影响（n=1000）

实验还在ANTI数据集通过改变线程数χ执行SMSQ协议。从图5可以看出，随着χ的增加，当d=2时，计算时间成本急剧下降。而且，当χ增加到一定程度时，计算时间成本将不再减少甚至增加。这是因为机器只有六个线程（一个用于DAP）。另一个原因是较大的χ会导致更多的合并开销。图6在n =1000时可以得出类似的结论。

图5 多线程查询性能（d=2）

图6 多线程查询性能（n=1000）