隱私保護(hù)的軌跡相似度計算方法

于海寧，張宏莉，余翔湛，曲家興，葛蒙蒙,3

（1.哈爾濱工業(yè)大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，黑龍江 哈爾濱 150001；2.黑龍江省網(wǎng)絡(luò)空間研究中心，黑龍江 哈爾濱 150001；3.南洋理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院，新加坡 639798）

0 引言

隨著無線通信、普適計算、衛(wèi)星導(dǎo)航技術(shù)的不斷發(fā)展，帶有GPS 定位功能的智能設(shè)備被應(yīng)用在許多領(lǐng)域[1]。這些設(shè)備能夠記錄相關(guān)實體的運動軌跡，進(jìn)而形成海量的軌跡數(shù)據(jù)。這些軌跡數(shù)據(jù)不但記錄了個體對象的運動模式、行為特征與規(guī)律，例如，經(jīng)?；顒拥穆肪€、生活工作的地點以及興趣愛好和健康狀況等，而且蘊含了群體對象的泛在移動模式與規(guī)律，例如，社會群體活動特征、城市交通擁堵規(guī)律、路網(wǎng)拓?fù)渑c地點坐標(biāo)等。針對海量的軌跡數(shù)據(jù)，人們通過軌跡分析、挖掘等技術(shù)手段進(jìn)行知識發(fā)現(xiàn)，并將其運用在各種交通和位置服務(wù)應(yīng)用中，包括交通導(dǎo)航、位置服務(wù)推薦、交通指揮、物流配送、車輛監(jiān)控等。軌跡相似度計算是軌跡分析的基礎(chǔ)操作之一，其主要分析不同軌跡之間的位置相似性。提取相似軌跡在出行路徑預(yù)測、興趣區(qū)域發(fā)現(xiàn)、軌跡聚類、個性化路徑推薦等領(lǐng)域具有廣泛的應(yīng)用。

云計算外包服務(wù)[2]的普及使很多軌跡擁有者選擇將軌跡上傳到云端軌跡服務(wù)存儲，以降低軌跡存儲和計算成本。同時，軌跡查詢者可以向軌跡服務(wù)發(fā)送關(guān)于其興趣軌跡的相似度計算請求，軌跡服務(wù)計算該興趣軌跡與存儲軌跡的相似度，并將最相似軌跡返回給查詢者。用戶在享受軌跡服務(wù)的同時，也面臨著嚴(yán)重的隱私泄露風(fēng)險[3]。軌跡數(shù)據(jù)中蘊含了大量關(guān)于用戶的私密信息[4]，例如用戶住址、經(jīng)濟(jì)和健康狀況等。軌跡服務(wù)往往會收集軌跡擁有者的上傳軌跡和軌跡查詢者的興趣軌跡，并從中挖掘用戶畫像。

針對上述隱私泄露問題，有研究提出了面向加密軌跡的軌跡相似度安全計算方法，其主要利用同態(tài)加密[5]、姚氏混淆電路[6]、安全求交集[7]等密碼學(xué)工具計算軌跡相似度，從而避免將軌跡泄露給軌跡服務(wù)[8-10]。例如，Liu 等[11]利用同態(tài)加密和姚氏混淆電路實現(xiàn)了軌跡相似度的安全計算框架，但該框架計算效率有待提升，例如，其計算2 條長度為100的軌跡之間的相似度大約需要13 min。

基于加密軌跡計算軌跡相似度是一個較復(fù)雜的問題，如何有效降低計算和通信開銷以適應(yīng)大規(guī)模、長軌跡的相似度計算是亟待解決的問題。本文聚焦大規(guī)模長軌跡的相似度安全計算，基于同態(tài)加密設(shè)計了隱私保護(hù)的軌跡相似度計算（pTSC,privacy-preserving trajectory similarity computation）方法，該方法能夠在保護(hù)用戶軌跡隱私的前提下，更高效地計算長軌跡之間的相似度。

本文主要的研究工作如下。

1) 提出了pTSC 方法，在該方法中軌跡服務(wù)存儲來自軌跡擁有者的加密上傳軌跡，接收來自軌跡查詢者的加密興趣軌跡，并支持基于密態(tài)的興趣軌跡和存儲軌跡的相似度安全計算，從而避免擁有者的軌跡和查詢者的查詢意圖泄露。

2) 提出了一個最長公共子序列安全計算（SLCSS）協(xié)議，該協(xié)議利用類同態(tài)加密算法和安全比較協(xié)議實現(xiàn)了基于密態(tài)軌跡的最長公共子序列計算。此外，該協(xié)議還設(shè)計了一種密文壓縮（簡稱Compress）算法，用以降低通信開銷。

3) 實現(xiàn)了pTSC 原型系統(tǒng)，并基于真實的軌跡數(shù)據(jù)集開展了性能開銷的仿真實驗，實驗結(jié)果表明，該方法具有良好的計算和通信性能，且優(yōu)于現(xiàn)有的計算方法。

1 預(yù)備知識

1.1 軌跡相似度計算

定義1軌跡。軌跡tr 是一個GPS 點的序列，tr=(p[0],p[1],…,p[m-1])，其中，p[i]=(x[i],y[j])，x[i]和y[i]分別為經(jīng)緯度坐標(biāo)。

最長公共子序列（LCSS,longest common subsequence）[12]用于衡量2 條軌跡的相似程度，其對軌跡噪聲具有較強(qiáng)的容忍度。給定 2 條軌跡tr1=(p1[0],…,p1[n-1])和 tr2=(p2[0],…,p2[m-1])，Head(tr1) 和 Head(tr2) 分別表示p1[0]和p2[0]，Rest(tr1)和 Rest(tr2)分別表示 (p1[1],…,p1[n-1])和(p2[1],…,p2[n-1])，那么，tr1和tr2之間的最長公共子序列表示為

其中，閾值∈用于判斷GPS 點是否鄰近。LCSS 的計算復(fù)雜度為(nm)。軌跡tr1和tr2的之間的LCSS相似度為

1.2 同態(tài)加密算法

類同態(tài)加密（SHE,somewhat homomorphic encryption）支持無限次密文加法以及有限次密文乘法。CKKS（Cheon-Kim-Kim-Song）同態(tài)加密算法[13]是基于環(huán)上錯誤學(xué)習(xí)（RLWE,ring learning with error）[14]的SHE 方案，具有語義安全性。CKKS同態(tài)加密算法概述如下。

如上所述，n個明文可以打包到一個密文中，且對打包后的密文進(jìn)行一次同態(tài)運算可以完成這n對明文的運算。

CKKS 同態(tài)加密算法還支持同態(tài)循環(huán)旋轉(zhuǎn)操作。假設(shè)一項密文對應(yīng)的明文多項式系數(shù)為m0,…,mn-1，那么，可以對密文做向右的k步同態(tài)循環(huán)旋轉(zhuǎn)操作來改變系數(shù)在明文多項式中的位置，獲得，其中，0≤k＜n，πk(i)=k+imodn。支持SIMD 向右的k步同態(tài)循環(huán)旋轉(zhuǎn)操作可表示為

1.3 安全比較協(xié)議

安全比較協(xié)議在不泄露雙方私密輸入值的前提下獲得2 個私密輸入值的大小關(guān)系。假設(shè)雙方各自持有l(wèi)bit 的私密輸入值，分別為x和y。它們可以執(zhí)行如下的安全比較協(xié)議[16]，以實現(xiàn)x和y的安全比較。

1) 雙方分別將各自的私密輸入值轉(zhuǎn)換為二進(jìn)制表示：x[l–1]x[l–2]…x[0]和y[l–1]y[l–2]…y[0]。

2) 當(dāng)i=l–1,l–2,…,0 時，雙方計算a[i]和b[i]如下。

如果i=l–1，則a[i]=x[i](1–y[i]),b[i]=y[i](1–x[i])。

如果i＜l–1，則a[i]=(1–b[i+1])(a[i+1]+(1–a[i+1])·x[i](1–y[i])),b[i]=(1–a[i+1])(b[i+1]+(1–b[i+1])y[i](1–x[i]))。

3) 最終比較結(jié)果判斷如下。

如果a[0]=1，則x>y。

如果b[0]=1，則x

如果a[0]=b[0]=0，則x=y。

2 模型與問題定義

2.1 系統(tǒng)模型

系統(tǒng)模型如圖1 所示，pTSC 主要涉及如下對象。

圖1 系統(tǒng)模型

軌跡服務(wù)（TS,trajectory service）：管理軌跡數(shù)據(jù)庫，對外提供軌跡外包存儲服務(wù)，并支持針對存儲軌跡的相似度計算服務(wù)。

密碼服務(wù)（CS,crypto service）：對外提供密鑰分發(fā)和管理服務(wù)，并參與軌跡相似度的安全計算。

軌跡擁有者：使用軌跡服務(wù)提供的存儲服務(wù)，以記錄其所擁有的歷史軌跡數(shù)據(jù)。

軌跡查詢者：使用軌跡服務(wù)提供的軌跡相似度計算服務(wù)，查詢與其興趣軌跡最近似的軌跡。

上述對象的交互流程概括如下。

1) 密碼服務(wù)生成一對公私鑰，公鑰被分發(fā)給其他對象，而私鑰被密碼服務(wù)保留。此步驟可以離線執(zhí)行。

2) 軌跡擁有者加密其軌跡，上傳至軌跡服務(wù)存儲。

3) 軌跡查詢者加密其興趣軌跡，向軌跡服務(wù)發(fā)起查詢請求，獲得與興趣軌跡最近似的存儲軌跡。

4) 軌跡服務(wù)聯(lián)合密碼服務(wù)基于加密軌跡計算相似度，檢索出與興趣軌跡最近似的存儲軌跡。

5) 軌跡服務(wù)將最近似的存儲軌跡及其相似度返回給軌跡查詢者。

2.2 威脅模型

pTSC 的威脅模型描述如下。

軌跡服務(wù)和密碼服務(wù)均是半誠實的，即雙方將嚴(yán)格地執(zhí)行協(xié)議，但是計算過程中它們會盡可能地根據(jù)中間信息和計算結(jié)果推測出更多的額外信息。針對半誠實模型的安全協(xié)議不但能夠?qū)崿F(xiàn)高效的計算，而且對惡意模型下的安全協(xié)議研究具有重要參考價值。

軌跡擁有者和軌跡查詢者均是半誠實的，前者會上傳其真實的加密軌跡信息，后者會提交其真實的加密查詢請求。

軌跡服務(wù)、密碼服務(wù)、軌跡擁有者和軌跡查詢者中任意兩方不存在共謀關(guān)系。此假設(shè)被廣泛認(rèn)可，因為軌跡服務(wù)和密碼服務(wù)提供商往往是信譽優(yōu)質(zhì)的大型企業(yè)，共謀行為會極大地?fù)p害聲譽。

底層通信網(wǎng)絡(luò)是安全的，不存在外部敵手竊聽或篡改通信內(nèi)容。

pTSC 面臨如下隱私威脅。

1) 軌跡跟蹤攻擊。軌跡服務(wù)或密碼服務(wù)獲取用戶的軌跡數(shù)據(jù)，實施針對目標(biāo)用戶的在線或離線跟蹤。

2) 大規(guī)模軌跡推理攻擊。軌跡服務(wù)或密碼服務(wù)收集大量用戶軌跡數(shù)據(jù)，并進(jìn)一步分析挖掘額外的用戶隱私信息，如家庭住址、經(jīng)濟(jì)或健康狀況等。

2.3 問題定義

本文關(guān)注的問題定義如下。

本文方法的設(shè)計目標(biāo)如下。

高性能。pTSC 方法應(yīng)該具有低的計算和通信開銷，在服務(wù)端支持高效的密態(tài)長軌跡相似度計算，在客戶端支持資源受限設(shè)備運行。

隱私保護(hù)。軌跡擁有者的存儲軌跡以及軌跡查詢者的興趣軌跡不會被泄露給軌跡服務(wù)和密碼服務(wù)。

3 pTSC 方法設(shè)計

本文提出的pTSC 方法可表示為pTSC=(Init,Upload,Query,SimComp)，如圖2 所示，其中，Init表示系統(tǒng)初始化，軌跡服務(wù)初始化系統(tǒng)參數(shù)，密碼服務(wù)生成一對公鑰和私鑰(pk,sk)，并公開pk，保留sk；Upload 表示軌跡上傳存儲；Query 表示軌跡查詢請求提交；SimComp 表示軌跡相似度安全計算。

圖2 pTSC 方法

3.1 軌跡上傳存儲

此外，軌跡擁有者構(gòu)造如下密文用于標(biāo)識軌跡trk的長度

3.2 軌跡查詢請求提交

軌跡查詢者加密查詢請求，并提交到軌跡服務(wù)查詢與其最近似的軌跡。假設(shè)軌跡查詢者持有興趣軌跡tr=(p[0],p[1],…,p[m–1])，其向軌跡服務(wù)發(fā)起查詢請求，以獲得與tr 最相似的軌跡。為此，查詢者構(gòu)造明文多項式，并使用CKKS 同態(tài)加密算法加密該多項式，進(jìn)而獲得加密的興趣軌跡其中

3.3 軌跡相似度安全計算

軌跡服務(wù)聯(lián)合密碼服務(wù)基于密態(tài)軌跡計算相似度，并將檢索結(jié)果返回給軌跡查詢者。假設(shè)軌跡服務(wù)存儲了M個擁有者的軌跡，擁有者owneri所屬的軌跡集合表示為，那么，軌跡服務(wù)存儲的密態(tài)軌跡集合可表示為

軌跡查詢者能夠指定軌跡擁有者的范圍，針對目標(biāo)擁有者的軌跡集合發(fā)起查詢請求。軌跡服務(wù)計算集合中每條密態(tài)存儲軌跡與興趣軌跡的相似度，并選擇出最近似的存儲軌跡作為查詢結(jié)果。

算法1軌跡相似度安全計算

算法1 具體步驟介紹如下。

圖3 2 條軌跡中GPS 點之間歐氏距離計算示例

圖4 密文壓縮示例

3) 軌跡服務(wù)基于壓縮后的距離密文，聯(lián)合密碼服務(wù)執(zhí)行安全計算協(xié)議，進(jìn)而計算出軌跡tr 與trk的最長公共子序列LCSS(tr,trk)，同時避免軌跡隱私泄露給軌跡服務(wù)或密碼服務(wù)。具體地，針對每一個壓縮距離密文，軌跡服務(wù)首先選擇n個? -1bit 的隨機(jī)整數(shù)（算法1 步驟10)），然后利用同態(tài)加法分別將這些隨機(jī)數(shù)加到壓縮密文對應(yīng)的明文多項式系數(shù)上，以達(dá)到保護(hù)有效距離值的目的（步驟11)）。軌跡服務(wù)將添加過隨機(jī)數(shù)的距離密文集合發(fā)送給密碼服務(wù)。密碼服務(wù)解密，并解碼明文多項式獲得一個添加了隨機(jī)數(shù)據(jù)的距離平方值的集合。

軌跡服務(wù)重復(fù)上述過程，計算出軌跡tr 與TR中所有軌跡之間的相似度，進(jìn)而選擇出與tr 最近似的軌跡 tr*返回給軌跡查詢者。

算法2密文壓縮算法

4 理論分析

4.1 復(fù)雜度分析

本文利用在線計算開銷和通信開銷分析pTSC 的復(fù)雜度。計算復(fù)雜度主要關(guān)注開銷較大的操作，例如，加解密、密文同態(tài)運算等，而忽視明文參與的相關(guān)運算。通信復(fù)雜度主要關(guān)注密文傳輸?shù)拈_銷。

在客戶端，軌跡擁有者對每條待上傳的軌跡需要執(zhí)行2 次加密操作，用以加密軌跡的經(jīng)緯度坐標(biāo)序列，同時向軌跡服務(wù)上傳3 個密文。軌跡查詢者每次查詢需要執(zhí)行2 次加密操作，同時向軌跡服務(wù)發(fā)送2 個密文。

在服務(wù)端，針對每次密態(tài)軌跡相似度計算，軌跡服務(wù)需要執(zhí)行2n次密文同態(tài)乘法，用以計算2 條軌跡GPS 點之間的距離平方值。軌跡服務(wù)執(zhí)行次同態(tài)循環(huán)旋轉(zhuǎn)操作將n個距離密文壓縮為個密文。壓縮后的密文被發(fā)送給密碼服務(wù)，密碼服務(wù)執(zhí)行β次解密操作，并執(zhí)行SLCSS協(xié)議。針對SLCSS，軌跡服務(wù)和密碼服務(wù)聯(lián)合執(zhí)行2β次安全比較。受益于SIMD 打包技術(shù)，針對這些安全比較，軌跡服務(wù)僅需執(zhí)行8 ?-7次同態(tài)乘法，密碼服務(wù)執(zhí)行? 次加密和一次解密。同時，軌跡服務(wù)和密碼服務(wù)之間需要傳輸 ?+1個密文。

CKKS 同態(tài)加密算法的多項式模度是影響pTSC 的主要指標(biāo)，其值取2 的整數(shù)次冪。多項式模度取值越大，方案安全性越高，但也會使密文尺寸變大，導(dǎo)致加密、解密、同態(tài)加法、同態(tài)乘法、同態(tài)旋轉(zhuǎn)等操作效率降低。

4.2 安全性分析

則稱服務(wù)端協(xié)議在半誠實攻擊者存在的條件下是安全的。

定理1pTSC 的服務(wù)端協(xié)議在半誠實攻擊者存在的條件下具有安全性。

證明針對如下2 個場景構(gòu)建多項式仿真者。

上述分析證明了pTSC 的服務(wù)端協(xié)議滿足定義2的安全性，其在半誠實攻擊者存在的條件下具有安全性。證畢。

pTSC 能夠解決2.2 節(jié)描述的隱私威脅，具體分析如下。

軌跡跟蹤攻擊。軌跡服務(wù)或密碼服務(wù)需要獲取用戶軌跡中的部分GPS 點信息來發(fā)起此攻擊。在pTSC 中，軌跡服務(wù)無法從CKKS 密文中獲取軌跡中任何GPS 點信息，甚至無法獲取存儲軌跡的長度。密碼服務(wù)同樣無法獲得任何軌跡信息。

大規(guī)模軌跡推理攻擊。軌跡服務(wù)或密碼服務(wù)可以通過獲取用戶軌跡中的部分GPS 點信息發(fā)起此攻擊，也可以引入一些攻擊背景知識通過關(guān)聯(lián)分析多條軌跡來發(fā)起此攻擊，例如分析軌跡長度、軌跡重疊來關(guān)聯(lián)已知的熱點線路。CKKS 同態(tài)加密算法滿足語義安全，因此，加密2 條相同的軌跡會得到2 個不可區(qū)分的密文。同時，軌跡服務(wù)也無法獲取存儲軌跡的長度。因此，軌跡服務(wù)無法對用戶軌跡開展有效的關(guān)聯(lián)分析。

5 實驗分析

本文采用微軟亞洲研究院Geolife 項目提供的GPS 軌跡數(shù)據(jù)集開展實驗，其由178 位用戶從2007 年4 月到2011 年10 月收集的17 621 條軌跡組成。本文使用SEAL 庫提供的CKKS 同態(tài)加密算法實現(xiàn)了pTSC 的原型，其中，CKKS 同態(tài)加密算法的多項式模度設(shè)置為n=4 096，距離有效值設(shè)置為κ=16 bit，屏蔽有效值的隨機(jī)數(shù)設(shè)置為?=32 bit。為了驗證本文方法的有效性，將其與文獻(xiàn)[11]方法對比。本文實驗環(huán)境如下：Ubuntu 18.04 LTS，英特爾i7-10700處理器2.9 GHz，16 GB 內(nèi)存。在此實驗環(huán)境下，CKKS 同態(tài)加密算法的開銷如表1 所示。

表1 CKKS 同態(tài)加密算法的開銷

客戶端計算開銷與存儲軌跡長度和興趣軌跡長度的關(guān)系如圖5 所示。從圖5 可以看出，pTSC在客戶端的計算開銷非常低，且不會受到存儲軌跡長度和興趣軌跡長度的影響。pTSC 在客戶端的計算開銷明顯少于文獻(xiàn)[11]方法。此外，當(dāng)興趣軌跡長度增長時，文獻(xiàn)[11]方法在客戶端的計算開銷隨之增加，這意味著當(dāng)興趣軌跡較長時，此方法會給客戶端帶來較大的計算開銷。

圖5 客戶端計算開銷

服務(wù)端計算開銷與存儲軌跡長度和興趣軌跡長度的關(guān)系如圖6 所示。從圖6 可以看出，pTSC在服務(wù)端的計算開銷不受存儲軌跡長度的影響，這是因為存儲軌跡長度是加密的，短存儲軌跡也不會減少計算開銷。然而，當(dāng)興趣軌跡長度增長時，pTSC 服務(wù)端的計算開銷線性增加，這是因為興趣軌跡長度是非加密的，長興趣軌跡會引發(fā)更多的GPS 點之間的距離的計算與比較。此外，服務(wù)端軌跡服務(wù)承擔(dān)了大部分計算開銷，而密碼服務(wù)的計算開銷非常低。文獻(xiàn)[11]方法在服務(wù)端的計算開銷較高，當(dāng)存儲軌跡長度或興趣軌跡長度增長時，計算開銷增加明顯，這導(dǎo)致此方法對長軌跡的相似度計算性能差，影響其可實踐性。pTSC 在服務(wù)端的計算開銷相比于文獻(xiàn)[11]方法降低了2 個數(shù)量級。

圖6 服務(wù)端計算開銷

客戶端與服務(wù)端之間的通信開銷與存儲軌跡長度和興趣軌跡長度的關(guān)系如圖7 所示。從圖7可以看出，pTSC 中服務(wù)端和客戶端之間的通信開銷很低，且不受存儲軌跡長度和興趣軌跡長度影響。然而，文獻(xiàn)[11]方法的通信開銷隨著興趣軌跡長度的增長而增大，這會增加客戶端資源受限設(shè)備的負(fù)擔(dān)。

圖7 客戶端與服務(wù)端之間的通信開銷

軌跡服務(wù)與密碼服務(wù)之間的通信開銷與存儲軌跡長度和興趣軌跡長度的關(guān)系如圖8 所示。從圖8(a)可以看出，pTSC 的服務(wù)端通信開銷較低，約為37.5 MB，且不受存儲軌跡長度影響。當(dāng)存儲軌跡長度較小時，文獻(xiàn)[11]方法的服務(wù)端通信開銷較低，但隨著存儲軌跡長度的增長，其通信開銷線性增加，且遠(yuǎn)高于pTSC 方法。從圖8(b)中可以看出，pTSC 的服務(wù)端通信開銷隨著興趣軌跡長度增長而線性增加，當(dāng)興趣軌跡長度由27增長到211時，通信開銷由18.8 MB 增加到294.3 MB；文獻(xiàn)[11]方法在服務(wù)端的開銷由65.9 MB 快速增加到1054.7 MB。綜上所述，pTSC 在服務(wù)端的通信性能明顯優(yōu)于文獻(xiàn)[11]方法。

圖8 軌跡服務(wù)與密碼服務(wù)之間的通信開銷

6 相關(guān)工作

軌跡相似度計算是軌跡分析領(lǐng)域的基礎(chǔ)操作之一，在明文下的計算方法已較為成熟，具體如下。1) 全局匹配算法，如DTW（dynamic time warping）、PDTW（piecewise dynamic time warping）等；2) 部分匹配算法，如LCSS、EDR（edit distance on real sequence）、ERP（edit distance with real penalty）等。為避免相似度計算時的軌跡泄露，一些隱私保護(hù)的軌跡相似度計算方法被提出，其通?；谕瑧B(tài)加密[5]、姚氏混淆電路[6]、安全求交集[7]等密碼學(xué)工具實現(xiàn)。PrivatePool[8]利用同態(tài)加密算法和安全求交集運算判斷軌跡GPS 點之間的鄰近程度，進(jìn)而推斷出軌跡間的重疊部分。TOPPool[9]在PrivatePool 基礎(chǔ)上考慮了軌跡的時間屬性，并優(yōu)化了安全求交集運算，以提升效率。SRide[10]利用同態(tài)加密和兩方安全等價測試來靈活地計算軌跡之前的重疊。類似的隱私保護(hù)的方法還包括文獻(xiàn)[17-19]提出的方法等。上述軌跡安全計算方法主要用于解決共乘安全規(guī)劃問題，通常這類問題涉及的軌跡長度較短。當(dāng)軌跡長度較長時，上述方法將面臨開銷過高的問題。針對更通用軌跡相似度安全計算，Zhu等[20]面向加密的時間序列提出了DTW 的兩方安全計算協(xié)議。許華杰等[21]綜合方向、速度、空間、時間方面的差異度量進(jìn)行相似度計算。Teng 等[22]提出了一種基于雙向相似度測量的安全軌跡相似性計算（SBD）方法，并使用簽名匹配過濾不同的軌跡，以降低開銷。Liu 等[11]利用同態(tài)加密和姚氏混淆電路設(shè)計了DTW、LCSS 和EDR 的安全計算框架。基于上述方法，Teng 等[23]構(gòu)建了加密軌跡搜索平臺SeTS3，該平臺支持DTW、LCSS 和SBD的安全計算。雖然上述方法在性能上取得了較大的提升，但仍難以應(yīng)對大規(guī)模的長軌跡安全計算，例如，針對2 條長度為100 的軌跡，文獻(xiàn)[11]方法計算一次LCSS 相似度大約需要13 min。相比于已有方法，pTSC 具有更低的計算和通信開銷。

7 結(jié)束語

為了解決軌跡外包服務(wù)中軌跡相似度計算的隱私泄露問題，本文提出了pTSC 方法。在該方法中，軌跡擁有者使用CKKS同態(tài)加密算法加密軌跡，并上傳到軌跡服務(wù)外包存儲；軌跡查詢者也使用CKKS 同態(tài)加密算法加密興趣軌跡，并向軌跡服務(wù)發(fā)起關(guān)于興趣軌跡的相似度查詢；軌跡服務(wù)基于密態(tài)興趣軌跡和存儲軌跡計算LCSS 相似度。此外，本文還設(shè)計了一個密文壓縮算法和密文安全比較協(xié)議，極大地提升了pTSC 的效率。理論分析和實驗結(jié)果表明，pTSC 具有安全性和高效性，且明顯優(yōu)于現(xiàn)有軌跡安全計算方法。