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

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

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

0 引言

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

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

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

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

1 相關(guān)知識

1.1 系統(tǒng)模型

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

圖1 系統(tǒng)模型

1.2 威脅模型

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

1.3 對稱向量隱藏加密算法

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

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

2 方案描述

本文設(shè)計(jì)了一種網(wǎng)格索引四叉樹結(jié)構(gòu)來實(shí)現(xiàn)高效且穩(wěn)定的任務(wù)分配效率，并采用SHVE 加密算法來保護(hù)索引樹及參與者的隱私安全。系統(tǒng)初始化階段，授權(quán)中心選擇安全參數(shù)λ并執(zhí)行SHVE.Setup(1λ) 來生成主密鑰msk。

2.1 網(wǎng)格索引四叉樹構(gòu)建

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

本文采用一種遞歸分解算法來進(jìn)行網(wǎng)格劃分并為每個網(wǎng)格生成唯一的二元標(biāo)識向量。遞歸分解的過程如下：

(1) 對經(jīng)度進(jìn)行二分，得到左右兩個子區(qū)間；

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

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

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

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

圖2 ρ=2 時建立網(wǎng)格索引四叉樹的流程

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

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

索引樹的構(gòu)建過程可視為網(wǎng)格遞歸分解的逆向過程，首先為所有網(wǎng)格建立節(jié)點(diǎn)作為葉子節(jié)點(diǎn)，然后向上逐層建立中間節(jié)點(diǎn)直至所有的節(jié)點(diǎn)匯聚為根節(jié)點(diǎn)。構(gòu)建索引樹的過程如下：

(1) 為所有網(wǎng)格創(chuàng)建對應(yīng)的葉子節(jié)點(diǎn)，并將網(wǎng)格的二元向量記為節(jié)點(diǎn)的標(biāo)識向量，特別地，每個葉子節(jié)點(diǎn)維護(hù)一個工作者隊(duì)列Q用于記錄可用工作者信息；

(2) 記(N0,N1,N2,N3)為處于同一子區(qū)域的4 個節(jié)點(diǎn)，Ni.g(0≤i≤3)表示節(jié)點(diǎn)的標(biāo)識向量，將這4 個節(jié)點(diǎn)作為子節(jié)點(diǎn)向上建立父節(jié)點(diǎn)，父節(jié)點(diǎn)的標(biāo)識向量計(jì)算為N0.g∧N1.g∧N2.g∧N3.g；

(3) 將上一步的結(jié)果作為輸入，重復(fù)步驟(2)直至輸出結(jié)果為根節(jié)點(diǎn)。

執(zhí)行上述過程，最終將生成一棵高度為ρ+1 的網(wǎng)格索引四叉樹。ρ=2 時生成的索引樹如圖2(b)所示。以圖2(a)的左上區(qū)域?yàn)槔紫葎?chuàng)建4 個葉子節(jié)點(diǎn)并記錄對應(yīng)的二元向量為節(jié)點(diǎn)標(biāo)識向量，然后向上建立父節(jié)點(diǎn)，并計(jì)算父節(jié)點(diǎn)的標(biāo)識向量為: (0000∧0001)∧(0010∧0011)=000*∧001*=00**。

其他節(jié)點(diǎn)的處理過程類似。此外，為了保護(hù)參與者的位置隱私安全，防止云服務(wù)器通過索引樹推測出用戶的真實(shí)位置信息，授權(quán)中心需要對索引樹的所有節(jié)點(diǎn)執(zhí)行SHVE.Gen 計(jì)算，將節(jié)點(diǎn)的標(biāo)識向量替換為陷門。最后，授權(quán)中心將索引樹發(fā)送給云服務(wù)器用于后續(xù)的任務(wù)分配服務(wù)。

2.2 位置上傳請求

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

2.3 任務(wù)分配請求

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

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

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)環(huán)境描述

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

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

3.2 理論分析

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

表1 理論分析符號表

(1) 索引樹中任意節(jié)點(diǎn)的生成包括一次標(biāo)識向量計(jì)算和一次SHVE.Gen 計(jì)算，前者的時間開銷為Tg，后者的時間開銷為2ρ(Tp+Txor)+Tenc。一棵高度為ρ+1 的索引樹的總節(jié)點(diǎn)數(shù)量為(4ρ+1-1)/3，因此，構(gòu)建索引樹的總時間開銷為(2ρ(Tp+Txor)+Tenc+Tg)(4ρ+1-1)/3。

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

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

3.3 實(shí)驗(yàn)結(jié)果分析

本節(jié)對實(shí)驗(yàn)結(jié)果進(jìn)行分析，首先分析了參數(shù)ρ對單位網(wǎng)格粒度的影響，然后展示了索引樹建立、位置上傳及任務(wù)分配3 方面的性能表現(xiàn)。

不同參數(shù)ρ下單位網(wǎng)格面積的演變趨勢如圖3 所示。理論上，ρ越大，劃分網(wǎng)格數(shù)量越多，單位網(wǎng)格面積越小，粒度越細(xì)。本文設(shè)置ρ=11 為本節(jié)實(shí)驗(yàn)的最大邊界值。在該參數(shù)下，數(shù)據(jù)集的覆蓋區(qū)域?qū)⒈粍澐譃?4×106個網(wǎng)格，單位網(wǎng)格面積約為0.255 m2，該粒度能夠滿足大部分現(xiàn)實(shí)應(yīng)用的精度需求。

圖3 不同ρ 下的單位網(wǎng)格面積

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

圖4 不同網(wǎng)格粒度下構(gòu)建索引樹的時間開銷

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

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

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

表2 方案對比

圖6 不同ρ 下的任務(wù)分配的時間開銷

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

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

4 結(jié)論

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