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）