一種高效的保護(hù)隱私的軌跡相似度計算框架

劉曙曙，劉 安，劉冠峰，李直旭，趙 雷，鄭 凱

（1．蘇州大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006；2．江蘇省軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心，南京 210008）

0 引 言

隨著移動通信和定位技術(shù)的發(fā)展，近年來涌現(xiàn)出各種各樣的移動定位設(shè)備，催生了一批基于軌跡數(shù)據(jù)的應(yīng)用，然而這也大大提高了個人私密信息被暴露的可能性．通過對個人運(yùn)動軌跡的攻擊性分析，某些時候可以準(zhǔn)確預(yù)測個人的興趣愛好，行為模式，生活習(xí)慣等個人隱私．比如，通過對某一用戶的日常軌跡進(jìn)行分析，攻擊者能夠迅速辨別出用戶的家庭住址和工作地址，從而為不法之徒提供了可乘之機(jī)．因此，軌跡隱私保護(hù)已經(jīng)成為普通用戶、工業(yè)界和學(xué)術(shù)界迫切關(guān)注的問題［1－2］．

在基于軌跡數(shù)據(jù)的應(yīng)用中，軌跡之間的相似度是一個重要的度量指標(biāo)，大量的與軌跡相關(guān)的分析和挖掘工作都需要進(jìn)行軌跡相似度的計算．本文主要研究如何安全、準(zhǔn)確、高效的計算軌跡相似度．具體來說，既要保證軌跡數(shù)據(jù)本身不被泄露，又要保證計算所得的軌跡相似度的準(zhǔn)確性．

1 軌跡隱私保護(hù)技術(shù)

近年來，軌跡數(shù)據(jù)的隱私保護(hù)問題得到了廣泛的重視［3］．在早期的研究工作中，主要通過對原始軌跡數(shù)據(jù)進(jìn)行一定程度的處理，在盡量保證軌跡數(shù)據(jù)可用的前提下，實(shí)現(xiàn)軌跡的隱私保護(hù)．主要可以分為假軌跡法、抑制法和泛化法三類［1］．泛化法是目前主流的軌跡隱私保護(hù)技術(shù)，軌跡k－匿名［4］是泛化法的代表．在位置k－匿名［5］技術(shù)中，它通過對移動對象在某一時刻的位置進(jìn)行泛化，從而保證這一時刻，該位置無法與其他k－1個用戶位置相區(qū)別．這一思想應(yīng)用于軌跡隱私保護(hù)技術(shù)中，產(chǎn)生了軌跡k－匿名，一般來說，k值越大則隱私保護(hù)效果越好，然而丟失的信息也越多．其不足之處在于，由于只適用于特定背景知識下的攻擊從而存在著嚴(yán)重的局限性［6］．

差分隱私［7－9］完美的解決了這一問題．與傳統(tǒng)隱私保護(hù)方法不同之處在于，差分隱私定義了一個極為嚴(yán)格的攻擊模型，并對隱私泄露風(fēng)險給出了嚴(yán)謹(jǐn)、定量化的表示和證明［10］，因此能夠防止攻擊者擁有任意背景知識下的攻擊并提供有力的保護(hù)．差分隱私保護(hù)方法的最大優(yōu)點(diǎn)是，雖然基于數(shù)據(jù)失真技術(shù)，但所加入的噪聲量與數(shù)據(jù)集大小無關(guān)，因此對于大型數(shù)據(jù)集，僅通過添加極少量的噪聲就能達(dá)到高級別的保護(hù)［10］．

盡管k－匿名和差分隱私技術(shù)能夠保證在不紕漏任何用戶軌跡隱私的情況下實(shí)現(xiàn)具有代表性的信息的發(fā)布，但是在本文中，我們需要計算的是兩用戶持有的軌跡數(shù)據(jù)之間的相似度，要求在計算中保證兩用戶的私有軌跡信息的隱私安全，故以上兩種技術(shù)并不適用．

2 問題定義

在本文中，我們假設(shè)存在兩個用戶Alice和Bob，他們分別持有一條軌跡數(shù)據(jù)．現(xiàn)Alice和Bob均希望得到彼此軌跡的相似度，同時又不希望將各自的軌跡數(shù)據(jù)暴露給對方．一種最直接的解決方法就是兩方將各自的軌跡數(shù)據(jù)都發(fā)送給一個可信的第三方，由第三方完成軌跡相似度的計算，并將結(jié)果反饋給他們．但是在實(shí)際生活中，完全可信賴的第三方是并不存在的．因此，如何在不泄露兩參與方軌跡數(shù)據(jù)的前提下，實(shí)現(xiàn)兩方軌跡相似度的計算是本文的關(guān)注點(diǎn)．

安全的軌跡相似度計算定義：Alice持有軌跡P＝［p1，p2，p3，…，p｜p｜］，Bob持有軌跡Q＝［q1，q2，q3，…，q｜q｜］，在不向?qū)Ψ叫孤盾壽E也不借助第三方的情況下，計算出兩方軌跡的相似度，并且雙方同時知道比較的結(jié)果．

攻擊模型：我們假設(shè)Alice和Bob都是半誠實(shí)的，兩方將嚴(yán)格的執(zhí)行協(xié)議，但是計算過程中兩方也會盡可能的根據(jù)中間信息推測出更多的額外信息．針對惡意攻擊模型的安全協(xié)議雖然存在，但是計算代價過大，在實(shí)際中并不實(shí)用．而針對半誠實(shí)模型的安全協(xié)議不但能夠?qū)崿F(xiàn)高效的計算，而且對惡意攻擊模型下的安全協(xié)議研究具有重要參考價值．

軌跡相似度［11］一般是軌跡點(diǎn)距離的聚合函數(shù)．目前比較常見的度量標(biāo)準(zhǔn)有Closest－Pair Distance（CPD），Sum－of－Pairs Distance（SPD），Dynamic Time Warping（DTW），Longest Common Subsequence（LCSS），Edit Distance with Real Penalty（ERP）和Edit Distance on Real Sequence（EDR）等．篇幅所限，本文僅僅使用DTW作為軌跡相似度的度量標(biāo)準(zhǔn)，但是本文提出的計算框架也很容易擴(kuò)展到其他軌跡相似度的度量標(biāo)準(zhǔn)．

在軌跡相似度實(shí)際使用中，我們將DTW算法分為兩個獨(dú)立步驟完成．在步驟一中，我們需要計算出兩條所有點(diǎn)對之間的歐氏距離的平方值（pi，qj）；在步驟二中，使用公式1中算法依次填充｜P｜×｜Q｜的矩陣M｜P｜｜Q｜．具體計算過程如下圖1所示．

圖1 基于DTW算法的軌跡相似度計算Fig．1 Computation of trajectory similarity based on DTWalgorithm

如圖1所示，Alice持有軌跡P＝［p1，p2，p3，…，p7］，Bob持有軌跡Q＝［q1，q2，q3，…，q5］，為了計算Alice和Bob的軌跡相似度，在步驟一中，我們需要計算出兩條軌跡所有點(diǎn)對之間的歐氏距離的平方值；在步驟二中，根據(jù)DTW算法用元素mi，j＝DTW（Pi，Qj）依次填充｜P｜×｜Q｜的軌跡相似度矩陣M｜P｜｜Q｜．矩陣頂角元素m｜P｜，｜Q｜＝133即為軌跡P和Q的相似度．由上可知，DTW算法的時間復(fù)雜度為O（｜P｜｜Q｜）．

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

3．1 基于同態(tài)加密的方法

Paillier加密系統(tǒng)［12］是Paillier于1999年發(fā)明的用于公鑰加密的概率非對稱算法．該加密系統(tǒng)具有加法同態(tài)性質(zhì)，即兩個密文乘積的解密值，與兩密文對應(yīng)明文的和相等，同時密文的k次冪解密值，與k和對應(yīng)明文的乘積相等．Paillier加密系統(tǒng)的語義安全特性保證了攻擊者無法由給定密文導(dǎo)出任何相關(guān)明文信息．

基于Paillier同態(tài)加密技術(shù)，Zhu等人提出了一個高效的保護(hù)隱私的時序數(shù)據(jù)相似度計算方法［13］．在步驟一中，利用Paillier加密系統(tǒng)的加法同態(tài)性質(zhì)，數(shù)據(jù)持有雙方可以方便基于密文計算出歐式距離的平方值［14－15］，其值以密文形式由一方持有．同時，Paillier加密系統(tǒng)的語義安全特性使得其能夠保證攻擊者無法由給定密文導(dǎo)出任何相關(guān)明文信息．在步驟二中，問題的關(guān)鍵是如何從三個值中安全有效的選出最小值．利用數(shù)據(jù)的保序特性，Zhu等人提出了一個安全的兩方協(xié)議進(jìn)行最小值計算，基于這個最小值計算協(xié)議和Paillier加密系統(tǒng)的同態(tài)性質(zhì)，我們可以順利完成軌跡相似度矩陣的填充，并保證數(shù)據(jù)信息安全無泄漏．

假設(shè)Alice的軌跡中｜P｜＝m，Bob的軌跡中｜Q｜＝n，k是最小值協(xié)議中為了達(dá)到干擾效果而添加的隨機(jī)數(shù)個數(shù)．那么在這一方案中，Bob端共需4mn次加密操作，4mn次解密操作，Alice端需要mn（k＋1）次加密操作．

盡管該方法能夠保證軌跡相似度計算過程中兩參與方數(shù)據(jù)的隱私安全，但是為了達(dá)到足夠的隱私安全，在最小值協(xié)議中為了達(dá)到干擾效果而添加的隨機(jī)數(shù)個數(shù)k必須足夠大，為此兩端都必須對額外的k個隨機(jī)數(shù)進(jìn)行額外的加解密操作，由此將產(chǎn)生大量額外的計算和通信開銷．

3．2 基于Yao協(xié)議的方法

Yao協(xié)議［16－17］允許兩個半誠實(shí)參與方分別輸入x和y作為一個任意函數(shù)f（x，y）的輸入，能夠準(zhǔn)確計算函數(shù)值并且保證除了最終結(jié)果外，沒有任何關(guān)于輸入或者中間值的相關(guān)信息泄露．為了實(shí)現(xiàn)軌跡相似度的計算，本文需要使用到2－MUL，2－ADD，2－SUB和2－MIN四個基本電路模塊［16，18］．他們都是利用Yao協(xié)議實(shí)現(xiàn)的Garbled Circuit基本模塊，其中，2－MUL可以實(shí)現(xiàn)任意L位整數(shù)之間的乘法，2－ADD可以實(shí)現(xiàn)任意兩個L位整數(shù)之間的加法，2－SUB與2－AND類似，2－MIN可以實(shí)現(xiàn)任意兩個L位整數(shù)之間的比較，輸出結(jié)果為較小值．

為了計算軌跡相似度，首先需要實(shí)現(xiàn)歐氏距離平方值計算單元和最小值選擇單元．利用歐式距離平方值計算電路單元，我們可以實(shí)現(xiàn)步驟一中兩軌跡所有點(diǎn)對之間歐式距離的平方值計算，其計算結(jié)果將以電路密文形式由Alice和Bob兩參與方共享．在步驟二中，利用最小值選擇單元和步驟一得到的歐氏距離平方值，可以順利完成相似度矩陣M｜P｜｜Q｜的填充，最終，只需對矩陣頂角元素m｜P｜，｜Q｜＝DTW（P，Q）解密，即可得到軌跡P和Q的相似度明文結(jié)果．

電路基本單元模塊設(shè)計如圖2所示，其中左邊為歐式距離平方值計算模塊，中間對應(yīng)相似度矩陣更新過程中邊界值更新，右邊對應(yīng)除邊界值外的其他單元格更新方法．基于這三個電路模塊，即可順利實(shí)現(xiàn)安全的軌跡相似度計算．

圖2 基于Yao協(xié)議的軌跡相似度計算的電路模塊設(shè)計Fig．2 Circuit module design of trajectory similary computation based on Yao’s protocol

在上面的電路模塊中，箭頭代表數(shù)據(jù)的流向，細(xì)線表示數(shù)據(jù)輸入為明文，粗線表示數(shù)據(jù)輸入為電路密文，電路密文使用兩參與方密鑰雙重加密而成，從而保證在兩參與方不勾結(jié)的情況下，任一方都無法獲取相關(guān)信息．在整個計算過程中，僅對最終結(jié)果m｜P｜，｜Q｜＝DTW（P，Q）解密，從而保證了計算過程中所有中間數(shù)據(jù)的安全性．

因?yàn)楫惢虿僮髟陔娐穼?shí)現(xiàn)中是免費(fèi)的［19］，所以在電路復(fù)雜度計算中，僅需討論除異或操作外的其他操作．Kolesnikov［18］指出，一個L－bit的加法單元可以通過L個1位的全加器實(shí)現(xiàn)，而實(shí)現(xiàn)1個1位的全加器需要借助1次與操作，故一個L－bit的加法器共需L次與操作．同理，可以統(tǒng)計得到一個L－bit的乘法單元共需與操作2L2－2L次；一個L－bit的最小值選擇單元共需與操作L次；一個L－bit的減法單元共需與操作L次．

當(dāng)Alice的軌跡中｜P｜＝m，Bob的軌跡中｜Q｜＝n，軌跡中經(jīng)緯度分別用L－bit的整數(shù)表示，分析可知，在DTW迭代計算過程中，共需調(diào)用歐式距離平方值計算模塊m＊n次，調(diào)用邊界更新模塊m＋n－2次，調(diào)用內(nèi)部更新電路模塊（m－1）（n－1）次．因此，軌跡相似度計算電路共需實(shí)現(xiàn)與操作16L2（2mn－m－n＋1）＋2L（mn＋2m＋2n－3）次．

3．3 結(jié)合同態(tài)加密和Yao協(xié)議的方法

通過觀察可以發(fā)現(xiàn)，在歐式距離平方值計算過程中，利用Yao協(xié)議實(shí)現(xiàn)的電路版本因?yàn)榇罅砍朔ê图臃娐返氖褂檬沟闷溆嬎銖?fù)雜度相對較高，由此帶來了大量的計算開銷和內(nèi)存消耗，相比之下，Paillier同態(tài)加密方法顯得更為實(shí)用．同樣，在矩陣相似度更新操作中，利用Paillier同態(tài)加密方法實(shí)現(xiàn)的最小選擇協(xié)議需要對大量隨機(jī)數(shù)進(jìn)行加解密操作，因而在性能上遠(yuǎn)不如Yao協(xié)議．于是提出了第三種方法，針對軌跡相似度計算過程中的不同步驟具有不同的計算特點(diǎn)，交替使用同態(tài)加密系統(tǒng)和Yao協(xié)議，從而高效地完成軌跡相似度計算．在這個方法中，兩軌跡所有點(diǎn)對之間的歐氏距離平方值運(yùn)算通過Paiiler同態(tài)加密方案實(shí)現(xiàn)，出于對中間數(shù)據(jù)的安全考慮和下一步中對Yao協(xié)議的輸入要求，我們要求最終結(jié)果必須以和的形式由兩參與方共享，現(xiàn)對算法進(jìn)行如下修改．

Alice：

（2）產(chǎn)生一系列隨機(jī)值R＝｛r1，r2，r3，…，r｜P｜＊｜Q｜｝，

Bob：

在步驟二中，我們對電路模塊做出如下調(diào)整，如圖3所示，左邊模塊用于相似度矩陣中的邊界值更新，右邊用于除邊界值外的其他單元格．

圖3 相似度矩陣更新模塊Fig．3 Updating module of similarity matrix

因?yàn)闅W式距離平方值計算和相似度矩陣更新是兩個獨(dú)立的部分，所以在復(fù)雜度分析時兩個部分單獨(dú)考慮．在歐式距離平方值計算部分，Alice需要3m＋mn次加密操作，Bob需要m次加密和mn次解密操作．在電路部分，共需實(shí)現(xiàn)與操作2L（4mn－2m－2n＋1）次．

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

對于以上提出的三種算法（為了方便討論，三種算法依次命名為DTW－Paillier，DTWYao和DTW－Hybrid），我們通過實(shí)驗(yàn)進(jìn)行了性能比較．實(shí)驗(yàn)用服務(wù)器的具體配置是：2．53 GHz CPU，256GB RAM，centos 7和JDK7．實(shí)驗(yàn)中，Alice和Bob之間的通信通過Socket實(shí)現(xiàn)，實(shí)驗(yàn)中不存在任何共享信息或可信第三方．

實(shí)驗(yàn)中，軌跡點(diǎn)的數(shù)據(jù)位數(shù)L一般設(shè)置為15位．為了保證加密數(shù)據(jù)的安全性，實(shí)驗(yàn)中統(tǒng)一使用1024位的Paillier加密系統(tǒng)進(jìn)行加解密操作，其安全性相當(dāng)于80位對稱密鑰，使用此加密方法加密后的數(shù)據(jù)披露風(fēng)險為1／280，在現(xiàn)實(shí)應(yīng)用中完全可以忽略不計．

為了測試軌跡長度對算法性能的影響，軌跡長度以步長為10從10增長到100．為了作圖方便，我們假設(shè)Alice和Bob持有的軌跡的具有相同的長度．

圖4比較了三種算法的運(yùn)行總時間．左圖為各算法在Alice端的運(yùn)行時間統(tǒng)計，右圖為各算法在Bob端的運(yùn)行時間統(tǒng)計．從圖中可以看到DTW－Paillier耗時最長，DTW－Yao其次，而本文提出的DTW－Hybrid效率最高．從第三節(jié)的復(fù)雜度分析中可以看出，盡管算法的運(yùn)行時間都與軌跡長度的平方成正比，但是得益于時間基數(shù)及比例系數(shù)優(yōu)勢，隨著軌跡長度不斷的增加，DTW－Hybrid算法的優(yōu)勢越來越突出，在軌跡長度為100時，效率提高近200倍．

圖4 DTW＿Paillier，DTW＿Yao和DTW＿Hybrid的性能比較Fig．4 Performance comparison about DTW＿Paillier，DTW＿Yao，and DTW＿Hybrid

如前所述，DTW＿Hybrid包含兩個階段：基于Paillier同態(tài)加密系統(tǒng)的歐氏距離平方值計算和基于Yao協(xié)議的相似度矩陣更新．我們分別對這兩個階段的時間進(jìn)行了統(tǒng)計．左圖為Alice端時間統(tǒng)計，右圖為Bob端時間統(tǒng)計，從圖5可以看到，兩個階段的時間與之前給出的計算復(fù)雜度理論分析基本一致．

圖5 歐式距離平方值計算和相似度矩陣更新的性能比較Fig．5 Performance comparison about computation of Euclidean distance squared and updating of similarity matrix

從圖5可以發(fā)現(xiàn)，在DTW＿Hybrid中，歐式距離平方值計算耗時相對較長，在整個方法中占據(jù)了75%左右．因此，對歐式距離平方值計算進(jìn)行進(jìn)一步優(yōu)化將有助于大幅度縮短算法的整體運(yùn)行時間．在實(shí)驗(yàn)中，利用并行技術(shù)對歐式距離平方值的計算進(jìn)行了進(jìn)一步優(yōu)化，優(yōu)化后的DTW＿Hybrid的性能如圖6所示．同樣，左圖為Alice端時間統(tǒng)計，右圖為Bob端時間統(tǒng)計．可以看到，在使用6個線程時，Alice的計算時間大約減少到原來的19%，而Bob的計算時間大約減少到原來的24%．

圖6 單線程和多線程的性能比較Fig．6 Performance comparison about single thread and muti thread

5 結(jié)論與展望

本文提出了一個保護(hù)隱私的軌跡相似度計算框架．該框架能夠確保持有軌跡的兩方不能得到除了軌跡相似度以外的其他任何信息，從而同時保護(hù)了兩方的軌跡數(shù)據(jù)隱私．該框架針對軌跡相似度的計算特點(diǎn)，通過結(jié)合同態(tài)加密和Yao協(xié)議，顯著提高了計算性能．實(shí)驗(yàn)結(jié)果表明本框架明顯優(yōu)于已有的保護(hù)隱私的軌跡相似度計算方法．通過分析目前常見的軌跡相似度度量標(biāo)準(zhǔn)，可知軌跡相似度計算主要涉及到歐式距離計算，最小值選擇或者最大值選擇等操作，這在本文提出的計算框架中均可得到高效地實(shí)現(xiàn)．下一步將在真實(shí)的軌跡數(shù)據(jù)上進(jìn)一步優(yōu)化本文提出的計算框架．

［1］霍崢，孟小峰．軌跡隱私保護(hù)技術(shù)研究［J］．計算機(jī)學(xué)報，2011，34（10）：1820－1830．

［2］霍崢，孟小峰，黃毅．PrivateCheckIn：一種移動社交網(wǎng)絡(luò)中的軌跡隱私保護(hù)方法［J］．計算機(jī)學(xué)報，2013，36（4）：716－726．

［3］CHEN L，?ZSU M T，ORIA V．Robust and fast similarity search for moving object trajectories［C］／／Proceedings of the 2005 ACM SIGMOD international conference on Management of data．ACM，2005：491－502．

［4］ABUL O，BONCHI F，NANNI M．Never walk alone：Uncertainty for anonymity in moving objects databases［C］／／Data Engineering，2008．ICDE2008．IEEE24th International Conference on．Ieee，2008：376－385．

［5］GRUTESER M，GRUNWALD D．Anonymous usage of location－based services through spatial and temporal cloaking［C］／／Proceedings of the 1st international conference on Mobile systems，applications and services．ACM，2003：31－42．

［6］LI N，LI T，VENKATASUBRAMANIAN S．t－closeness：Privacy beyond k－anonymity and l－diversity［C］／／Data Engineering，2007．ICDE2007．IEEE23rd International Conference on．IEEE，2007：106－115．

［7］DWORK C．Differential privacy［M］／／Encyclopedia of Cryptography and Security．US：Springer，2011：338－340．

［8］DWORK C．Differential privacy：A survey of results［M］／／Theory and Applications of Models of Computation．Berlin Heidelberg：Springer，2008：1－19．

［9］DWORK C，LEI J．Differential privacy and robust statistics［C］／／Proceedings of the forty－first annual ACM symposium on Theory of computing．ACM，2009：371－380．

［10］張嘯劍，孟小峰．面向數(shù)據(jù)發(fā)布和分析的差分隱私保護(hù)［J］．計算機(jī)學(xué)報，2014（4）：018．

［11］DENG K，XIE K，ZHENG K，et al．Trajectory indexing and retrieval［M］／／Computing with spatial trajectories．New York：Springer，2011：35－60．

［12］PAILLIER P．PUBLIC－key cryptosystems based on composite degree residuosity classes［C］／／Advances in cryptology－EUROCRYPT＇99．Berlin Heidelberg：Springer，1999：223－238．

［13］ZHU H，MENG X，KOLLIOS G．Privacy Preserving Similarity Evaluation of Time Series Data［C］／／EDBT，2014：499－510．

［14］INAN A，KANTARCIOGLU M，BERTINO E，et al．A hybrid approach to private record linkage［C］／／Data Engineering，2008．ICDE2008．IEEE24th International Conference on．IEEE，2008：496－505．

［15］HU H，XU J，REN C，et al．Processing private queries over untrusted data cloud through privacy homomorphism［C］／／Data Engineering（ICDE），2011 IEEE27th International Conference on．IEEE，2011：601－612．

［16］YAO A C C．How to generate and exchange secrets［C］／／Foundations of Computer Science，1986．27th Annual Symposium on．IEEE，1986：162－167．

［17］LINDELL Y，PINKAS B．A proof of security of Yao＇s protocol for two－party computation［J］．Journal of Cryptology，2009，22（2）：161－188．

［18］KOLESNIKOV V，SADEGHI A R，SCHNEIDER T．Improved garbled circuit building blocks and applications to auctions and computing minima［M］／／Cryptology and Network Security．Springer Berlin Heidelberg，2009：1－20．

［19］KOLESNIKOV V，SCHNEIDER T．Improved garbled circuit：Free XOR gates and applications［M］／／Automata，Languages and Programming．Berlin Heidelberg：Springer，2008：486－498．