基于加密數據的安全多方Skyline查詢協議

在云服務器上，針對密文數據進行大規模Skyline查詢是一項現有挑戰。由于密文計算，現有的安全Skyline查詢方案會產生大量的通信和計算成本。因此，本文利用加法同態和代理重加密來加密數據集，并基于該加密數據集進行Skyline查詢計算。然而，基于該密碼系統的安全計算將進一步降低查詢效率。因此，為了提高加密數據的計算效率，本研究重新設計了兩個輕量級的安全比較協議。同時，提出了“blind-reading”的有效方法來安全地獲取Skyline點。接著，通過設計的隱私矩陣來減少數據集的規模，從而在不泄露隱私的情況下顯著降低計算成本。然后，通過集成輕量級安全比較協議、“blind-reading”和隱私矩陣技術來構建安全Skyline查詢協議。最后，其性能評估表明，與現有技術相比，所提出的方法顯著提高了效率（至少快了4.5倍），并且在大型數據集下具有良好的可擴展性。

該成果“Ef?cient 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）