空間眾包中一種支持高效任務分配的隱私保護方案

李惟佳，李軍義，龔志茂，譚湘杰

（1.湖南大學 校園信息化建設與管理辦公室，湖南 長沙 410082；2.湖南大學 信息科學與工程學院，湖南 長沙 410082）

0 引言

眾包[1](Crowdsourcing)是一類新興的分布式工作模式，是指將原本由機構或個人完成的任務通過互聯網公開招募的方式外包給大量未知網絡人群的一種行為。作為一種符合國家發展的全新經濟模式，眾包服務已被廣泛應用于現實生活中，《中華人民共和國國民經濟和社會發展第十四個五年規劃和2035 年遠景目標綱要》第十五章也明確指出:“深入推進服務業數字化轉型，培育眾包設計、智慧物流、新零售等新增長點。”空間眾包[2](Spatial Crowdsourcing)是眾包與地理位置緊密結合的產物，其中包含3 類實體，分別為任務請求者（以下簡稱請求者）、任務工作者（以下簡稱工作者）和云服務器。請求者將任務發布至云服務器，工作者從云服務器上選擇任務并物理移動到指定位置來執行任務。

由于工作者不可能時刻關注任務列表，為了保證任務被執行率，云服務器通常會設計一種任務分配方法來自動分配任務。當收到來自請求者的任務后，云服務器按照分配規則將其分配給合適的在線工作者。位置是任務分配過程中的一項重要評估指標，為了保證任務分配的質量，防止出現超出預期的分配誤差，云服務器需要周期性地收集在線工作者的實時位置。然而值得注意的是，云服務器并非完全可信的實體，一方面，它可以提供正確的服務；另一方面，它可能會在未經授權的情況下非法訪問用戶的敏感數據，并推測出個人隱私。例如，云服務器可以利用工作者的連續位置數據繪制軌跡圖來分析行為規律，也可以利用任務位置來推測請求者的家庭住址、工作單位等敏感信息[3-4]。特別是當位置與醫療服務相關時，惡意的服務提供者可能會利用這一信息不公正地決定是否接收其保險和勞務合同[5]。

為了解決這一問題，近年來研究者們提出了幾種基于位置的可搜索加密方案[6-10]保護參與者的位置數據安全。用戶先在本地加密位置信息然后僅將密文上傳至云服務器，云服務器會在密文上進行任務分配。然而，這些方案無法保證任務分配的高效性，因為加密在保護數據隱私的同時會帶來額外的計算開銷。一些方案僅支持線性時間復雜度的任務分配服務，單次任務分配的時間開銷需要十幾分鐘甚至幾個小時；另外一些方案針對效率問題進行了改進，支持了次線性時間復雜度的任務分配服務，然而這些方案的時間開銷不具備穩定性，整體開銷會隨在線工作者數量的增加而增加，無法滿足當前大數據時代的需求。

針對這一挑戰，本文提出了一種基于索引樹的可搜索加密方案，在保護參與者雙向位置隱私安全的同時支持高效且穩定的任務分配服務。具體而言，本文采用一種遞歸分解算法將眾包區域劃分為若干網格并為每個網格生成唯一二元標識向量，然后提出了一種自下而上的索引樹構建算法來生成一棵網格索引四叉樹。為了保護參與者的位置隱私安全，本文使用一種對稱隱藏向量加密算法SHVE(Symmetric-key Hidden Vector Encryption)[11]。實驗分析展示了本文方案各方面的性能表現，與現有工作相比，本文所提出的方案在任務分配方面的性能表現更優。尤其是當索引樹高度固定時，本文方案在任務分配方面的時間開銷是穩定的，不受在線工作者數量影響。

1 相關知識

1.1 系統模型

本文方案的系統模型如圖1 所示，其中包含4 類實體：授權中心、請求者、工作者和云服務器。授權中心是一個完全可信的第三方實體，負責生成系統密鑰和索引樹，并管理用戶的注冊和注銷。請求者向云服務器發起眾包任務，服務器則按照預先約定的規則將任務分配給合適的工作者。最后，接受任務的工作者需要物理移動到任務所指定的位置來完成任務。

圖1 系統模型

1.2 威脅模型

本文假定云服務器是一類“誠實但好奇”的實體，這一假設被廣泛應用于現有的隱私保護工作中[12-14]。具體而言，一方面云服務器被認為是誠實的，能夠提供正確的服務且不會惡意地修改數據；另一方面，云服務器是好奇的，渴望收集更多的額外信息來獲取更高的利益。

1.3 對稱向量隱藏加密算法

SHVE 是一種支持在密文上進行合取的對稱向量隱藏加密算法。定義F0表示一個偽隨機函數，E0表示一種支持加密計算Enc 和解密計算Dec 的對稱加密算法，Γ表示一個有限屬性集合{0,1}，*表示不存在于Γ中的通配符，Γ*表示Γ∪{*}，SHVE 算法可描述為如下4 部分：

如果μ=0λ+logλ，系統輸出True，表示密文與陷門匹配成功；否則輸出⊥，表示無法正確執行。

2 方案描述

本文設計了一種網格索引四叉樹結構來實現高效且穩定的任務分配效率，并采用SHVE 加密算法來保護索引樹及參與者的隱私安全。系統初始化階段，授權中心選擇安全參數λ并執行SHVE.Setup(1λ) 來生成主密鑰msk。

2.1 網格索引四叉樹構建

利用網格思想將原本復雜的坐標距離計算轉換為更為簡單的網格比較是空間眾包隱私保護研究中的常用方法之一。對于大小為T×T的空間區域，可將其劃分為若干大小相等的網格，并將同一網格內的所有位置坐標歸一到網格中心坐標。換句話說，如果兩個用戶位于同一網格，則他們被認為處于同一位置。

本文采用一種遞歸分解算法來進行網格劃分并為每個網格生成唯一的二元標識向量。遞歸分解的過程如下：

(1) 對經度進行二分，得到左右兩個子區間；

(2) 對緯度進行二分，得到上下兩個子區間；

(3) 對得到的4 個子區域按照左上、左下、右上、右下的順序分別編碼為00、01、10、11；

(4) 如果精度未達到要求，將上面得到的4 個子區域分別作為輸入重復上述操作。

假設預期精度為ρ，區域最終被分解為22ρ個網格，每個網格對應一個2ρ位長的二元標識向量。ρ=2 時的遞歸分解過程如圖2(a)所示。區域首先被分解為4 個部分，然后每個子區域再進行遞歸分解。圖中給出了左上子區域的第二輪遞歸示例，其他區域同理，每個網格的向量由父區域編碼與子區域編碼拼接而成，例如0001 由00 與01 拼接而成。

圖2 ρ=2 時建立網格索引四叉樹的流程

網格劃分完成之后，本文設計了一種自下而上的構建算法來創建一棵網格索引四叉樹。在描述索引樹構建流程之前給出向量計算符∧的定義：對于任意兩個m比特的向量v,w∈，如果存在一個向量p∈滿足

其中，1≤l≤m，則有v∧w=p。例如，向量1001 和1000 僅在第四個比特值不同，因此可以計算得到1001∧1000=100*。

索引樹的構建過程可視為網格遞歸分解的逆向過程，首先為所有網格建立節點作為葉子節點，然后向上逐層建立中間節點直至所有的節點匯聚為根節點。構建索引樹的過程如下：

(1) 為所有網格創建對應的葉子節點，并將網格的二元向量記為節點的標識向量，特別地，每個葉子節點維護一個工作者隊列Q用于記錄可用工作者信息；

(2) 記(N0,N1,N2,N3)為處于同一子區域的4 個節點，Ni.g(0≤i≤3)表示節點的標識向量，將這4 個節點作為子節點向上建立父節點，父節點的標識向量計算為N0.g∧N1.g∧N2.g∧N3.g；

(3) 將上一步的結果作為輸入，重復步驟(2)直至輸出結果為根節點。

執行上述過程，最終將生成一棵高度為ρ+1 的網格索引四叉樹。ρ=2 時生成的索引樹如圖2(b)所示。以圖2(a)的左上區域為例，首先創建4 個葉子節點并記錄對應的二元向量為節點標識向量，然后向上建立父節點，并計算父節點的標識向量為: (0000∧0001)∧(0010∧0011)=000*∧001*=00**。

其他節點的處理過程類似。此外，為了保護參與者的位置隱私安全，防止云服務器通過索引樹推測出用戶的真實位置信息，授權中心需要對索引樹的所有節點執行SHVE.Gen 計算，將節點的標識向量替換為陷門。最后，授權中心將索引樹發送給云服務器用于后續的任務分配服務。

2.2 位置上傳請求

工作者向授權中心注冊以獲取密鑰。為了防止隱私泄露，每一輪位置上傳過程中，工作者先在本地加密位置信息，然后提交密文數據至云服務器。假設工作者本輪需要上傳的地理坐標為(xw,yw)，首先將地理坐標轉換為所在網格的二元標識向量gw，然后執行SHVE.Enc(gw,msk)得到，最后將上傳至云服務器。

2.3 任務分配請求

類似地，請求者也需要先向授權中心注冊以獲取密鑰。假設請求者發起任務的地理坐標為(xt,yt)，首先將地理坐標轉換為所在網格的向量標識符gt，然后執行SHVE.Enc(gt,msk)得到，最后將和任務內容發送至云服務器。

最后，云服務器最終將任務內容下發給候選工作者，工作者可以選擇接受或者拒絕任務。如果沒有工作者接受任務，云服務器將任務掛起并在下一輪分配流程中重新計算。

3 實驗分析

3.1 實驗環境描述

本文方案通過Python3 實現，其中SHVE 算法的安全參數λ=128，E0選為AES 算法，運行環境為Ubuntu 22.04，2 Intel(R) Xeon(R) Silver 4110 CPU @ 2.10 GHz,128 GB RAM。

本文實驗數據取自于真實數據集Gowalla，其中包含來自196 591 名用戶的6 442 890 條帶有位置坐標的打卡記錄。本文從Gowalla 數據集中選取緯度在(30.26,30.27)，經度在(-97.75,-97.74)區間內的共51 959 條數據作為測試數據集。為了避免實驗結果的偶然性，實驗結果皆為多次實驗的平均值。本文還將方案ETA[7]、Priradar[8]、GPSC[9]和PPTA[10]用于對比。ETA 是一種基于Paillier[15]的安全準確任務分配協議；Priradar 是一種基于變色龍哈希的位置隱私保護框架；GPSC 是一種基于Bloom 過濾器[16]的網格隱私保護方案；PPTA 是一種同時支持在線任務分配和批量任務分配的靈活的位置隱私保護方案，公平起見，下文對比實驗中的數據僅記錄其在線任務分配設置下的性能表現。

3.2 理論分析

本節使用到的符號及其相應的含義如表1 所示，指定參數ρ，本文方案將生成一棵高度為ρ+1 的索引樹，其中每個節點的標識向量長度為2ρ，此時單次SHVE.Gen、SHVE.Enc 和SHVE.Query 計算的時間開銷分別為2ρ(Tp+Txor)+Tenc、2ρTp和2ρTxor+Tdec。本節將分別對索引樹構建、位置上傳和任務分配進行理論分析。

表1 理論分析符號表

(1) 索引樹中任意節點的生成包括一次標識向量計算和一次SHVE.Gen 計算，前者的時間開銷為Tg，后者的時間開銷為2ρ(Tp+Txor)+Tenc。一棵高度為ρ+1 的索引樹的總節點數量為(4ρ+1-1)/3，因此，構建索引樹的總時間開銷為(2ρ(Tp+Txor)+Tenc+Tg)(4ρ+1-1)/3。

(2) 工作者位置上傳流程包括一次SHVE.Enc 計算和一次深度優先檢索，前者的時間開銷為2ρTp，后者則需要進行O(ρ+1)次節點檢索。對于每個檢索節點，需要執行一次SHVE.Query 計算，整個檢索過程的時間開銷可表示為O(ρ+1) (2ρTxor+Tdec)。因此，工作者位置上傳流程的總時間開銷為2ρTp+O(ρ+1) (2ρTxor+Tdec)。

(3) 請求者任務分配流程包括一次SHVE.Enc 計算、一次深度優先檢索和一次任務分配計算，其中前兩個部分的整體時間開銷為2ρTp+O(ρ+1) (2ρTxor+Tdec)。任務分配也可視為一次節點檢索流程，時間開銷與所訪問的節點數量相關，記為O(n)。因此，請求者任務分配流程的總時間開銷為2ρTp+O(ρ+1)(2ρTxor+Tdec)+O(n)。

3.3 實驗結果分析

本節對實驗結果進行分析，首先分析了參數ρ對單位網格粒度的影響，然后展示了索引樹建立、位置上傳及任務分配3 方面的性能表現。

不同參數ρ下單位網格面積的演變趨勢如圖3 所示。理論上，ρ越大，劃分網格數量越多，單位網格面積越小，粒度越細。本文設置ρ=11 為本節實驗的最大邊界值。在該參數下，數據集的覆蓋區域將被劃分為 4×106個網格，單位網格面積約為0.255 m2，該粒度能夠滿足大部分現實應用的精度需求。

圖3 不同ρ 下的單位網格面積

不同粒度下構建一棵網格四叉索引樹的時間開銷如圖4 所示。理論分析中指出，構建索引樹的時間開銷僅與ρ正向相關。粒度越小，ρ越大，建索引樹的理論時間開銷也越大，圖中的曲線變化趨勢也反映了這一結論。從實驗結果來看，構建一棵細粒度的索引樹的時間開銷是不容忽視的。然而，索引樹只需要在系統初始化階段構建一次，即使后續需要更改，授權中心也可以預先計算。因此，在實際生產中，該部分的時間成本是可以接受的。

圖4 不同網格粒度下構建索引樹的時間開銷

不同參數ρ下位置上傳請求的時間開銷如圖5 所示。位置上傳請求的時間成本主要來源于兩個部分：工作者本地加密和索引樹深度優先搜索計算。加密部分的時間開銷受加密算法和密鑰復雜度的影響，該部分時間開銷視為恒定的，因為這些配置在系統初始化階段被選定且不會改變。而深度優先搜索的時間開銷則可表示為O(ρ+1)，其中ρ+1 表示為索引樹高度。這意味著位置上傳請求的時間開銷將與ρ正向相關，這與圖中曲線趨勢一致。值得注意的是，當ρ=11 時，位置上傳請求的執行時間僅約為1.34 ms，該延時在實際應用中往往是難以察覺的，這也意味著即使在高粒度的網格劃分中本文方案依然能夠支持高效的位置上傳請求。

圖5 不同ρ 下的位置上傳的時間開銷

不同參數ρ下任務分配請求時間開銷如圖6 所示，其中工作者數量固定為10 000，任務位置固定為區域中心坐標。任務分配請求的時間成本主要來源于3 個部分：請求者本地加密、索引樹深度優先搜索和任務分配。正如上面所分析的，本地加密部分的時間開銷是恒定的，深度優先搜索部分的時間開銷與ρ正向相關。任務分配部分的時間開銷取決于檢索節點數量。但是，由于該部分不涉及密文計算，其時間開銷是可以忽略的。因此，圖中的時間曲線與圖5 相似，且同樣維持在毫秒級別。為了展示本文方案在任務分配方面的性能表現，本文設置ρ=11 并將工作者的數量從2 000 增加到10 000，然后隨機選擇1 000 個坐標作為任務位置，最后的平均時間開銷記錄如表2 所示。從實驗結果可知，本文所提出的方案在性能表現上優于現有的所有方案，能夠在毫秒級別處理單個任務分配請求。此外，不同于現有工作，當索引樹的高度固定時，本文方案在任務分配方面的時間開銷還具有穩定性。這是因為本文方案在任務分配方面的時間開銷主要集中在本地加密和深度搜索計算方面，而這兩部分的時間開銷僅與ρ正向相關，與在線工作者數量無關。

表2 方案對比

圖6 不同ρ 下的任務分配的時間開銷

定義密文下的實際分配距離為dc，明文下的理論最優分配距離為dp，任務分配的相對距離誤差可以表示為e=|dc-dp|。一般而言，相對距離誤差越小，任務分配質量越高。不同參數ρ下的任務分配請求的相對距離誤差如圖7 所示。2.1 小節指出位于同一網格內的工作者將被視為位于網格中心坐標，即他們分配任務的概率是均等的。理論上，工作者的真實坐標與網格中心坐標之間存在一定的偏差，且單位網格面積越小，偏差范圍越小。圖3 指出，ρ越大時單位網格面積越小，即ρ越大，偏差范圍越小，此時的相對距離誤差也就越小，任務分配質量也就越高。圖中曲線證實了這一理論。

圖7 不同ρ 下的任務分配的相對距離誤差

4 結論

隨著移動設備和無線互聯網的發展，空間眾包服務近些年得到了大力發展，同時也暴露了一些安全問題。本文關注于空間眾包服務中的位置隱私泄露問題，提出了一種支持高效任務分配的可搜索加密方案來保護參與者的位置信息免受半誠實的云服務器的侵犯。具體而言，本文首先提出了一種基于網格的索引四叉樹結構來保證任務分配計算的高效性，然后采用了一種對稱隱藏加密算法來保障參與者及索引樹的安全性。大量基于真實數據集的實驗表明，本文方案在大規模工作者數量場景中的任務分配性能表現優于現有其他工作。