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

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

0 引言

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

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

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

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

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

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

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

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

1 預(yù)備知識(shí)

1.1 軌跡相似度計(jì)算

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

最長(zhǎng)公共子序列（LCSS,longest common subsequence）[12]用于衡量2 條軌跡的相似程度，其對(duì)軌跡噪聲具有較強(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之間的最長(zhǎng)公共子序列表示為

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

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

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

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

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

1.3 安全比較協(xié)議

安全比較協(xié)議在不泄露雙方私密輸入值的前提下獲得2 個(gè)私密輸入值的大小關(guān)系。假設(shè)雙方各自持有l(wèi)bit 的私密輸入值，分別為x和y。它們可以執(zhí)行如下的安全比較協(xié)議[16]，以實(shí)現(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 時(shí)，雙方計(jì)算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 模型與問(wèn)題定義

2.1 系統(tǒng)模型

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

圖1 系統(tǒng)模型

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

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

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

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

上述對(duì)象的交互流程概括如下。

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

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

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

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

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

2.2 威脅模型

pTSC 的威脅模型描述如下。

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

軌跡擁有者和軌跡查詢者均是半誠(chéng)實(shí)的，前者會(huì)上傳其真實(shí)的加密軌跡信息，后者會(huì)提交其真實(shí)的加密查詢請(qǐng)求。

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

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

pTSC 面臨如下隱私威脅。

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

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

2.3 問(wèn)題定義

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

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

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

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

3 pTSC 方法設(shè)計(jì)

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

圖2 pTSC 方法

3.1 軌跡上傳存儲(chǔ)

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

3.2 軌跡查詢請(qǐng)求提交

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

3.3 軌跡相似度安全計(jì)算

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

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

算法1軌跡相似度安全計(jì)算

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

圖3 2 條軌跡中GPS 點(diǎn)之間歐氏距離計(jì)算示例

圖4 密文壓縮示例

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

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

算法2密文壓縮算法

4 理論分析

4.1 復(fù)雜度分析

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

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

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

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

4.2 安全性分析

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

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

證明針對(duì)如下2 個(gè)場(chǎng)景構(gòu)建多項(xiàng)式仿真者。

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

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

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

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

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

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

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

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

圖5 客戶端計(jì)算開(kāi)銷

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

圖6 服務(wù)端計(jì)算開(kāi)銷

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

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

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

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

6 相關(guān)工作

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

7 結(jié)束語(yǔ)

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