一種身份認(rèn)證下交換查詢的軌跡位置保護(hù)算法

李 蘭，張才寶，奚舒舒，馬鴻洋

1(青島理工大學(xué) 信息與控制工程學(xué)院，山東 青島 266525)2(青島理工大學(xué) 理學(xué)院，山東 青島 266033)

E-mail:17864213324@163.com

1 引 言

無線通信和全球定位技術(shù)的飛速發(fā)展給移動應(yīng)用程序帶來了新的機(jī)遇，許多嵌入基于位置服務(wù)[1-4](Location-Based-Service,LBS)功能 的APP被開發(fā)出來，用戶可以在陌生的環(huán)境中使用這類APP查詢附近的酒店、超市等興趣點[5](Point of Interest,POI)來滿足自身需求，這些應(yīng)用程序給日常生活提供了諸多便利[6,7].但隨著用戶安全意識的提高，在享受LBS服務(wù)的同時，用戶也時刻擔(dān)心提交給位置服務(wù)提供商(Location Service Provider,LSP)(以下LSP與LBS服務(wù)器指代同一個對象)的信息被不法分子截取.用戶主要考慮兩個方面，第一，使用此類APP時需通過手機(jī)號獲取驗證碼進(jìn)行登錄，此時，用戶的手機(jī)號會被LSP獲?。坏诙?，使用時用戶需要提交查詢信息，并將自身位置發(fā)送給LSP，此時，用戶的查詢內(nèi)容和位置信息會被LSP獲取.由于實名制度的實施，手機(jī)號碼可作為用戶的真實身份之一[8]，當(dāng)惡意攻擊者將手機(jī)號碼與用戶提交的查詢內(nèi)容和位置信息鏈接后，容易推斷出用戶的興趣、住址等隱私[9]，因此目前的工作是如何有效解決這兩個問題.

2 相關(guān)工作

目前，對于連續(xù)查詢中用戶的軌跡隱私保護(hù)已經(jīng)引起廣泛關(guān)注.Huo等[10]提出對軌跡信息上的敏感點進(jìn)行匿名化的方法，以保護(hù)軌跡隱私.Hwang等[11]提出了一種根據(jù)用戶隱私檔案和環(huán)境條件形成隱藏區(qū)域的時間模糊技術(shù)，使得惡意LBS服務(wù)器無法重建用戶軌跡.Palanisamy等[12，13]利用混合區(qū)提供黑箱空間，截斷各子軌跡所反映的相關(guān)性，降低攻擊者關(guān)聯(lián)整個軌跡的成功概率，之后又提出將用戶形成一個隱匿區(qū)域，除查詢發(fā)起者外，該區(qū)域還包含其他k-1個用戶，這樣，對手就無法確定發(fā)起者用戶.Jiang[14]等提出一種基于查詢分片用戶協(xié)作的位置隱私保護(hù)方法，用于解決實際應(yīng)用環(huán)境中協(xié)作用戶的不可信問題.還有基于原語的密碼學(xué)方法[15,16]，通過對用戶與LBS服務(wù)器的交互信息加密實現(xiàn)隱私保護(hù)目的，可以提供很好的安全性，但存在用戶與LBS服務(wù)器通訊中計算開銷很大的問題.

身份認(rèn)證是移動用戶使用LBS功能應(yīng)用程序的基礎(chǔ)，手機(jī)號碼和姓名、住址等一樣，代表著用戶的真實信息，如果不法分子將用戶的網(wǎng)絡(luò)信息與真實信息關(guān)聯(lián)起來，用戶的隱私會遭到泄露.Wang等[17]提出一種通過第三方平臺存儲個人信息的模型，為用戶提供個性化信息推送服務(wù).Gu等[18]提出一種數(shù)字簽名技術(shù)與身份認(rèn)證方案，該方案結(jié)合橢圓曲線密碼體制與組合式偽隨機(jī)數(shù)，并使用SVO邏輯對該方案進(jìn)行形式化分析.Wang等[19]提出基于PTPM(portable TPM)和無證書公鑰簽名算法的身份認(rèn)證方案，支持用戶利用任意終端設(shè)備來完成與云端的雙向身份認(rèn)證過程，以解決目前云環(huán)境下用戶與云端之間進(jìn)行身份認(rèn)證時所存在的安全問題和不足.Zhou等[20]提出可證安全的高效無證書兩方認(rèn)證密鑰協(xié)商協(xié)議.類似于文獻(xiàn)[19,20]主要集中在利用公鑰證書進(jìn)行身份認(rèn)證的研究，而基于短信驗證碼的身份認(rèn)證的安全性的研究較少.

本文提出一種身份認(rèn)證下交換查詢的軌跡位置保護(hù)算法.用戶登錄時，利用可信第三方服務(wù)器，將數(shù)據(jù)進(jìn)行分割，該服務(wù)器保存用戶的手機(jī)號碼，LSP保存與用戶真實身份無關(guān)的數(shù)據(jù).當(dāng)用戶進(jìn)行查詢時，根據(jù)用戶的隱私需求構(gòu)建候選協(xié)同用戶區(qū)域，利用距離權(quán)重計算方法，選擇熵最大的一個用戶作為最佳協(xié)同用戶(Best Collaborative User,BCU)，使雙方互相交換查詢內(nèi)容.這樣既保護(hù)了用戶的真實身份，又保護(hù)了位置隱私，即使LBS服務(wù)器被不法分子攻擊，也無法對用戶進(jìn)行準(zhǔn)確識別，有效保護(hù)用戶隱私安全.

3 身份認(rèn)證下交換查詢的軌跡位置保護(hù)算法

本節(jié)首先定義了一些基本概念，然后給出身份認(rèn)證下交換查詢的軌跡保護(hù)模型，本文使用的符號匯總在表1中.

表1 符號匯總Table 1 Symbol summary

3.1 相關(guān)定義

定義 1.(距離度量)用戶ui和uj之間的距離度量(本文使用歐幾里得距離)，定義為

(1)

其中x，y分別表示用戶所在位置的經(jīng)度和緯度.

定義 2.(距離權(quán)重)用αi表示查詢用戶ureal的候選協(xié)同用戶區(qū)域內(nèi)用戶ui的距離權(quán)重，定義為

(2)

定義 3.(最佳協(xié)同用戶)k個候選協(xié)同用戶中權(quán)重最大的一個稱為最佳協(xié)同用戶，表示為

(3)

3.2 系統(tǒng)模型

本文系統(tǒng)架構(gòu)如圖1所示，軌跡隱私保護(hù)模塊由移動用戶、第三方服務(wù)器及LBS服務(wù)器(LSP)組成；身份認(rèn)證模塊由移動用戶、可信第三方服務(wù)器、LBS服務(wù)器(LSP)及短信平臺組成.

圖1 系統(tǒng)架構(gòu)Fig.1 System structure

軌跡隱私保護(hù)算法中，第三方服務(wù)器根據(jù)定義2中的距離權(quán)重計算αi，并選擇BCU輔助用戶進(jìn)行查詢，BCU的選擇如圖2所示.

圖2 候選協(xié)同用戶區(qū)域Fig.2 Candidate collaborative user area

3.3 移動用戶身份認(rèn)證

為了防止LBS服務(wù)器泄露用戶的隱私信息，本文在移動用戶與LBS服務(wù)器間引入可信第三方服務(wù)器，將原來存儲在LBS服務(wù)器上的手機(jī)號碼分離出來，存儲在第三方服務(wù)器上，從而防止由手機(jī)號碼引起的用戶隱私信息的泄露.架構(gòu)圖如圖1身份認(rèn)證模塊所示，具體步驟如下：

步驟1.移動用戶輸入TelePhone,將獲取短信驗證碼的請求發(fā)送給可信第三方服務(wù)器.

步驟2.可信第三方服務(wù)器將TelePhone過濾,并將包含用戶ID和本次會話號的請求發(fā)送給LBS服務(wù)器.

步驟3.LBS服務(wù)器通過特定算法生成短信驗證碼,與購買的短信平臺服務(wù)權(quán)限和用戶ID一起發(fā)送給可信第三方服務(wù)器.

步驟4.可信第三方服務(wù)器將TelePhone和短信驗證碼發(fā)給短信平臺.

步驟5.短信平臺將驗證碼發(fā)往用戶端,用戶使用驗證碼登錄.

用戶端通過驗證碼登錄后，LSP通過用戶提交的驗證碼與自己生成的驗證碼進(jìn)行比較，若相同，則驗證通過.

因為可信第三方服務(wù)器沒有購買短信平臺服務(wù)權(quán)限，所以LSP需要將該服務(wù)權(quán)限發(fā)送給第三方服務(wù)器，本文通過算法1進(jìn)行該權(quán)限的處理.

算法1.授予訪問權(quán)限

輸入：IDLSP：LSP的ID

輸出：授權(quán)結(jié)果Res

1.LSP通過算法產(chǎn)生一個隨機(jī)序列Seq；

2.LSP利用私鑰將序列Seq加密；

3.Seq～=Private Key{Seq}；

4.LSP將{Seq～,IDLSP}發(fā)送給可信第三方服務(wù)器；

5.可信第三方服務(wù)器將{Seq～,IDLSP}發(fā)送給短信平臺；

6.短信平臺根據(jù)LSP的公鑰對消息進(jìn)行驗證：

7.Res=Public Key{{Seq～,IDLSP}};

8.returnRes

3.4 基于交換查詢的軌跡位置保護(hù)算法

第三方服務(wù)器根據(jù)用戶的隱私需求構(gòu)建候選協(xié)同用戶區(qū)，通過距離權(quán)重選擇BCU，然后將用戶與BCU的ID轉(zhuǎn)換，并發(fā)送給LSP進(jìn)行查詢，LSP將查詢結(jié)果返回給第三方服務(wù)器后，再將用戶和BCU的ID恢復(fù)，并分別將結(jié)果發(fā)送給用戶和BCU.具體步驟如下：

步驟1.用戶將查詢消息EU2A發(fā)送給第三方服務(wù)器，其中隱私需求使用第三方服務(wù)器公鑰加密，查詢內(nèi)容和范圍以及對稱加密密鑰使用LBS服務(wù)器公鑰加密，第三方服務(wù)器使用私鑰獲得用戶的隱私需求，尋找協(xié)同用戶，并將距離權(quán)重最大的一個設(shè)為最佳協(xié)同用戶BCU.EU2A形式如下(4)：

EU2A={PKA(ID,Rmin,Rmax,k),PKS(R,Q,KS)}

(4)

步驟2.找到BCU后，第三方服務(wù)器將用戶的ID轉(zhuǎn)換成BCU的偽ID(IDBi)，然后將IDBi與用戶的查詢請求共同組成查詢消息，如式(5)所示：

EA2S={PKS(IDBi),PKS(R,Q,KS)}

(5)

第三方服務(wù)器將用戶的查詢消息發(fā)送給LBS服務(wù)器，值得注意的是，用戶的查詢內(nèi)容和范圍使用LBS服務(wù)器公鑰加密，所以第三方服務(wù)器無法獲得.

步驟3.LBS服務(wù)器收到消息EA2S后，進(jìn)行解密，并根據(jù)用戶的需求搜索POI并獲得結(jié)果E，最后它使用對稱加密密鑰加密E，將其發(fā)送給第三方服務(wù)器.

ES2A={PKA(IDBi),KS(E)}

(6)

步驟4.第三方服務(wù)器收到來自LBS服務(wù)器的查詢結(jié)果后，首先從列表中恢復(fù)用戶的ID，然后利用用戶公鑰將提取出來的查詢結(jié)果KS(E)進(jìn)行加密，如式(7)所示：

EA2U={PKU(KS(E))}

(7)

最后，第三方服務(wù)器將查詢結(jié)果發(fā)送給用戶.

步驟5.用戶從第三方服務(wù)器收到EA2U后，使用私鑰和對稱加密密鑰獲得精確結(jié)果E.在查詢交換過程中，第三方服務(wù)器同樣為最佳協(xié)同用戶BCU執(zhí)行步驟1-步驟4.

尋找最佳協(xié)同用戶算法偽代碼如算法2所示

算法2.尋找最佳協(xié)同用戶

輸入：ID,Rmin,Rmax,k

輸出：最佳協(xié)同用戶BCU

1.初始化隊列q，并設(shè)置|q|=k；

2.根據(jù)用戶隱私需求，輸入Rmin、Rmax和k，如果用戶不輸入k值，默認(rèn)k=6，構(gòu)建候選協(xié)同用戶區(qū)域；

3.從候選協(xié)同用戶區(qū)域中選擇k個用戶，并放入隊列q中；

4.if協(xié)同用戶數(shù)量小于kthen

5. 協(xié)同用戶數(shù)量不足，k=k-1；

6.else

7.fori=1tokdo

8. 計算距離權(quán)重αi；

10.endif

4 安全性分析

本文的安全性分析集中在如何保護(hù)用戶的真實身份和軌跡隱私，主要針對竊聽攻擊、不可信LBS服務(wù)器及第三方服務(wù)器攻擊.

4.1 竊聽攻擊

用戶與第三方服務(wù)器之間以及第三方服務(wù)器與LBS服務(wù)器之間的通信過程可以被攻擊者通過無線信道竊聽.軌跡隱私保護(hù)模塊中使用對消息加密的方式來處理竊聽攻擊，在無線信道中傳輸?shù)乃邢⒍加煞菍ΨQ和對稱密鑰加密保護(hù).

當(dāng)用戶向第三方服務(wù)器發(fā)送查詢消息時，隱私需求使用第三方服務(wù)器公鑰加密為PKA(ID,Rmin,Rmax,k)，查詢內(nèi)容、范圍和對稱加密密鑰使用LBS服務(wù)器公鑰加密為PKS(R,Q,K_S)，然后將EU2A={PKA(ID,Rmin,Rmax,k),PKS(R,Q,KS)}發(fā)送給第三方服務(wù)器，在此過程中，攻擊者沒有第三方服務(wù)器和LBS服務(wù)器的私鑰，即使竊聽到消息，也無法得到任何信息.同樣，當(dāng)?shù)谌椒?wù)器將ID轉(zhuǎn)換后的查詢請求EA2S={PKS(IDBi),PKS(R,Q,KS)}發(fā)送給LBS服務(wù)器時，攻擊者無法獲得任何信息，因此用戶的敏感信息得到有效保護(hù).

返回查詢結(jié)果時，ES2A={PKA(IDBi),KS(E)}使用第三方服務(wù)器公鑰和對稱加密密鑰加密，EA2U={PKU(KS(E))}使用用戶的公鑰加密，攻擊者沒有第三方服務(wù)器私鑰、對稱加密密鑰和用戶的私鑰，因此，他們獲取有用信息的概率可以忽略不計.通過以上分析，可以看到我們的方案可以有效抵抗竊聽者的攻擊，使攻擊者無法獲得用戶的真實身份、查詢位置和查詢內(nèi)容.

4.2 不可信LBS服務(wù)器

LSP管理用戶的所有查詢信息，當(dāng)LSP不是受信任時，可以通過這些數(shù)據(jù)推斷敏感信息，包括用戶的真實身份和移動軌跡.

本文的方案中，因為手機(jī)號碼存儲在可信第三方平臺，而不是LBS服務(wù)器，所以，即使攻擊者通過LBS服務(wù)器獲得了用戶信息，也無法和真實信息聯(lián)系起來，有效保護(hù)用戶的身份.并且在軌跡隱私保護(hù)模塊中，第三方服務(wù)器在用戶和BCU之間交換查詢，在這個過程中，用戶的身份ID在第i個查詢中被BCU的IDBi替換，并且LBS服務(wù)器中的查詢信息存儲記錄被鏈接到BCU的IDBi.由于每個查詢點的BCU不同，LSP無法推斷他們之間的關(guān)系，也無法從任意BCU的IDBi中識別用戶的真實軌跡.因此，LSP能夠推斷用戶真實身份或其軌跡的概率可以忽略不計.

4.3 第三方服務(wù)器攻擊

身份認(rèn)證模塊中，假設(shè)Bob通過第三方服務(wù)器得到了Alice的信息{TelePhone,ID}.Bob企圖使用Alice的“TelePhone+短信驗證碼”進(jìn)行登錄，由于Bob沒有Alice的手機(jī)，無法獲得短信驗證碼，因此登錄失敗；同理，如果Bob用Alice的“ID+PassWord”進(jìn)行登錄，由于Bob無法獲知Alice的PassWord，同樣登錄失敗.

軌跡隱私保護(hù)模塊中，Bob通過第三方服務(wù)器得到了Alice的查詢消息EU2A={PKA(ID,Rmin,Rmax,k),PKS(R,Q,KS)}，即使Bob使用第三方服務(wù)器私鑰獲得了Alice的ID，但因為缺少LBS服務(wù)器私鑰SKS，無法解密Alice的查詢內(nèi)容和范圍；同樣，假設(shè)Bob通過第三方服務(wù)器得到Alice的查詢結(jié)果ES2A={PKA(IDBi),KS(E)}，由于Bob沒有對稱加密密鑰KS，無法解密查詢結(jié)果E，因此Bob無法獲得關(guān)于Alice的有效信息.

5 實驗仿真

5.1 實驗環(huán)境

實驗環(huán)境為2.4GHz的雙核CPU，8GB內(nèi)存，操作系統(tǒng)是Windows10.在身份認(rèn)證模塊中，本文在MySQL(線程池中的20個線程)上模擬通信時間；軌跡隱私保護(hù)模塊中，算法采用Python編程語言實現(xiàn)，在Thomas Brinkhoff[21]上進(jìn)行仿真實驗，在Oldenburg交通路網(wǎng)中取大約4km×4km區(qū)域位置數(shù)據(jù)，其中20個POIs是隨機(jī)生成的，用戶數(shù)量由參數(shù)控制.

5.2 仿真結(jié)果分析

5.2.1 身份認(rèn)證中時間效率分析

實驗時從數(shù)據(jù)庫表中采集了所有用戶登錄時請求記錄數(shù)總和n的值，當(dāng)n分別為600,800,1000,1200時，處理每一次請求所花費的時間(ms)，x軸表示實驗重復(fù)次數(shù).

由圖3可以看出，第一次實驗時的請求響應(yīng)時間比后面7次響應(yīng)時間大，這是因為系統(tǒng)初始化后需要重新連接數(shù)據(jù)庫.

將圖3中n分別為600,800,1000,1200時的8次模擬數(shù)據(jù)取平均值得到圖4.

圖3 請求記錄數(shù)與響應(yīng)時間關(guān)系Fig.3 Relationship between number of request records and response time圖4 不同n值下的平均響應(yīng)時間Fig.4 Average response time at different values of n

由圖4可以看出，當(dāng)請求記錄數(shù)量達(dá)到1200時，系統(tǒng)平均響應(yīng)時間未達(dá)到5000ms，即5s，現(xiàn)在短信平臺響應(yīng)時間普遍在5s以內(nèi)，所以總響應(yīng)時間可以保持在10s以內(nèi)，而短信驗證碼的有效時間為60s，所以此身份認(rèn)證方案在實際應(yīng)用中是可行的，既保護(hù)了用戶的隱私信息，又能較好的為用戶提供服務(wù).

5.2.2 基于交換查詢的軌跡隱私保護(hù)算法分析

為驗證軌跡隱私保護(hù)算法的有效性，本文在請求響應(yīng)時間和用戶軌跡位置保護(hù)程度兩方面與CPP算法[22]進(jìn)行比較，為增加說服力，兩種算法中用戶的Rmin與Rmax均相同.

系統(tǒng)響應(yīng)時間指用戶的請求通過某算法進(jìn)行處理后發(fā)送給LSP，并收到從LBS服務(wù)器返回的第一個POI的這段時間.

由圖5可以看出，兩種算法的系統(tǒng)響應(yīng)時間隨k值的增大而增加.當(dāng)k很小時，用戶可以很快尋找到協(xié)同用戶或者生成匿名區(qū)域，但當(dāng)k值增加到一定程度時，系統(tǒng)響應(yīng)時間明顯增加，這是因為k值越大，用戶搜索其他k-1個用戶的時間越久.圖5中明顯看出，本文基于交換查詢的軌跡隱私保護(hù)算法的響應(yīng)時間比CPP算法短，因為在找到協(xié)同用戶后，系統(tǒng)只需要分別計算協(xié)同用戶的權(quán)重即可，而CPP算法需要根據(jù)約束條件生成匿名區(qū)，增加了響應(yīng)時長.

圖5 系統(tǒng)響應(yīng)時間與k值的關(guān)系Fig.5 Relationship between system response time and k value圖6 軌跡位置保護(hù)度與k值的關(guān)系Fig.6 Relationship between protection degree of track position and k value

在可接受的系統(tǒng)響應(yīng)時間下，用戶軌跡位置保護(hù)程度是衡量算法優(yōu)劣的的重要指標(biāo).圖6為本文基于交換查詢的軌跡隱私保護(hù)算法與CPP算法在用戶軌跡位置保護(hù)程度上的對比.

由圖6可以看出，當(dāng)k值較小時，兩種算法由于無法構(gòu)建良好的輔助區(qū)域，在用戶軌跡保護(hù)程度上接近，隨著k值增加，本文基于交換查詢的軌跡隱私保護(hù)算法明顯可以達(dá)到更好的保護(hù)效果.這是因為k值增加到一定程度時，可以從眾多協(xié)同用戶中選擇距離權(quán)重最大的一個作為BCU，且最佳協(xié)同用戶是動態(tài)變化的，攻擊者無法將用戶在各個時刻上的位置聯(lián)系起來，因此k值越大，本文基于交換查詢的軌跡隱私保護(hù)算法對用戶的軌跡保護(hù)程度越高.

6 結(jié)束語

為了更好地保護(hù)用戶的真實身份、位置信息與查詢內(nèi)容，防止惡意攻擊者通過LSP將用戶的這些信息聯(lián)系起來，提出一種身份認(rèn)證下交換查詢的軌跡位置保護(hù)算法.用戶登錄時利用第三方服務(wù)器將手機(jī)號碼過濾，使LSP無法獲得用戶的手機(jī)號碼；當(dāng)用戶向LSP提交位置信息和查詢請求時，利用BCU與用戶進(jìn)行交換查詢，使LSP無法關(guān)聯(lián)用戶的查詢請求與ID.最后通過仿真實驗，驗證了該算法在保護(hù)用戶身份與軌跡隱私方面的有效性.從不同方面考慮協(xié)同用戶的選擇是本課題將繼續(xù)研究的內(nèi)容.