隱私保護的軌跡相似度計算方法

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

（1.哈爾濱工業大學網絡空間安全學院，黑龍江 哈爾濱 150001；2.黑龍江省網絡空間研究中心，黑龍江 哈爾濱 150001；3.南洋理工大學計算機科學與工程學院，新加坡 639798）

0 引言

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

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

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

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

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

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

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

3) 實現了pTSC 原型系統，并基于真實的軌跡數據集開展了性能開銷的仿真實驗，實驗結果表明，該方法具有良好的計算和通信性能，且優于現有的計算方法。

1 預備知識

1.1 軌跡相似度計算

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

最長公共子序列（LCSS,longest common subsequence）[12]用于衡量2 條軌跡的相似程度，其對軌跡噪聲具有較強的容忍度。給定 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 的計算復雜度為(nm)。軌跡tr1和tr2的之間的LCSS相似度為

1.2 同態加密算法

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

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

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

1.3 安全比較協議

安全比較協議在不泄露雙方私密輸入值的前提下獲得2 個私密輸入值的大小關系。假設雙方各自持有lbit 的私密輸入值，分別為x和y。它們可以執行如下的安全比較協議[16]，以實現x和y的安全比較。

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

2) 當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) 最終比較結果判斷如下。

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

如果b[0]=1，則x

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

2 模型與問題定義

2.1 系統模型

系統模型如圖1 所示，pTSC 主要涉及如下對象。

圖1 系統模型

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

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

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

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

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

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

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

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

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

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

2.2 威脅模型

pTSC 的威脅模型描述如下。

軌跡服務和密碼服務均是半誠實的，即雙方將嚴格地執行協議，但是計算過程中它們會盡可能地根據中間信息和計算結果推測出更多的額外信息。針對半誠實模型的安全協議不但能夠實現高效的計算，而且對惡意模型下的安全協議研究具有重要參考價值。

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

軌跡服務、密碼服務、軌跡擁有者和軌跡查詢者中任意兩方不存在共謀關系。此假設被廣泛認可，因為軌跡服務和密碼服務提供商往往是信譽優質的大型企業，共謀行為會極大地損害聲譽。

底層通信網絡是安全的，不存在外部敵手竊聽或篡改通信內容。

pTSC 面臨如下隱私威脅。

1) 軌跡跟蹤攻擊。軌跡服務或密碼服務獲取用戶的軌跡數據，實施針對目標用戶的在線或離線跟蹤。

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

2.3 問題定義

本文關注的問題定義如下。

本文方法的設計目標如下。

高性能。pTSC 方法應該具有低的計算和通信開銷，在服務端支持高效的密態長軌跡相似度計算，在客戶端支持資源受限設備運行。

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

3 pTSC 方法設計

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

圖2 pTSC 方法

3.1 軌跡上傳存儲

此外，軌跡擁有者構造如下密文用于標識軌跡trk的長度

3.2 軌跡查詢請求提交

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

3.3 軌跡相似度安全計算

軌跡服務聯合密碼服務基于密態軌跡計算相似度，并將檢索結果返回給軌跡查詢者。假設軌跡服務存儲了M個擁有者的軌跡，擁有者owneri所屬的軌跡集合表示為，那么，軌跡服務存儲的密態軌跡集合可表示為

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

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

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

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

圖4 密文壓縮示例

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

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

算法2密文壓縮算法

4 理論分析

4.1 復雜度分析

本文利用在線計算開銷和通信開銷分析pTSC 的復雜度。計算復雜度主要關注開銷較大的操作，例如，加解密、密文同態運算等，而忽視明文參與的相關運算。通信復雜度主要關注密文傳輸的開銷。

在客戶端，軌跡擁有者對每條待上傳的軌跡需要執行2 次加密操作，用以加密軌跡的經緯度坐標序列，同時向軌跡服務上傳3 個密文。軌跡查詢者每次查詢需要執行2 次加密操作，同時向軌跡服務發送2 個密文。

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

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

4.2 安全性分析

則稱服務端協議在半誠實攻擊者存在的條件下是安全的。

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

證明針對如下2 個場景構建多項式仿真者。

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

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

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

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

5 實驗分析

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

表1 CKKS 同態加密算法的開銷

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

圖5 客戶端計算開銷

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

圖6 服務端計算開銷

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

圖7 客戶端與服務端之間的通信開銷

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

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

6 相關工作

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

7 結束語

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