一種身份認證下交換查詢的軌跡位置保護算法

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

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

E-mail:17864213324@163.com

1 引 言

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

2 相關工作

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

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

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

3 身份認證下交換查詢的軌跡位置保護算法

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

表1 符號匯總Table 1 Symbol summary

3.1 相關定義

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

(1)

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

定義 2.(距離權重)用αi表示查詢用戶ureal的候選協同用戶區域內用戶ui的距離權重，定義為

(2)

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

(3)

3.2 系統模型

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

圖1 系統架構Fig.1 System structure

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

圖2 候選協同用戶區域Fig.2 Candidate collaborative user area

3.3 移動用戶身份認證

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

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

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

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

步驟4.可信第三方服務器將TelePhone和短信驗證碼發給短信平臺.

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

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

因為可信第三方服務器沒有購買短信平臺服務權限，所以LSP需要將該服務權限發送給第三方服務器，本文通過算法1進行該權限的處理.

算法1.授予訪問權限

輸入：IDLSP：LSP的ID

輸出：授權結果Res

1.LSP通過算法產生一個隨機序列Seq；

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

3.Seq～=Private Key{Seq}；

4.LSP將{Seq～,IDLSP}發送給可信第三方服務器；

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

6.短信平臺根據LSP的公鑰對消息進行驗證：

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

8.returnRes

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

第三方服務器根據用戶的隱私需求構建候選協同用戶區，通過距離權重選擇BCU，然后將用戶與BCU的ID轉換，并發送給LSP進行查詢，LSP將查詢結果返回給第三方服務器后，再將用戶和BCU的ID恢復，并分別將結果發送給用戶和BCU.具體步驟如下：

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

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

(4)

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

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

(5)

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

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

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

(6)

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

EA2U={PKU(KS(E))}

(7)

最后，第三方服務器將查詢結果發送給用戶.

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

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

算法2.尋找最佳協同用戶

輸入：ID,Rmin,Rmax,k

輸出：最佳協同用戶BCU

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

2.根據用戶隱私需求，輸入Rmin、Rmax和k，如果用戶不輸入k值，默認k=6，構建候選協同用戶區域；

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

4.if協同用戶數量小于kthen

5. 協同用戶數量不足，k=k-1；

6.else

7.fori=1tokdo

8. 計算距離權重αi；

10.endif

4 安全性分析

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

4.1 竊聽攻擊

用戶與第三方服務器之間以及第三方服務器與LBS服務器之間的通信過程可以被攻擊者通過無線信道竊聽.軌跡隱私保護模塊中使用對消息加密的方式來處理竊聽攻擊，在無線信道中傳輸的所有消息都由非對稱和對稱密鑰加密保護.

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

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

4.2 不可信LBS服務器

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

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

4.3 第三方服務器攻擊

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

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

5 實驗仿真

5.1 實驗環境

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

5.2 仿真結果分析

5.2.1 身份認證中時間效率分析

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

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

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

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

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

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

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

系統響應時間指用戶的請求通過某算法進行處理后發送給LSP，并收到從LBS服務器返回的第一個POI的這段時間.

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

圖5 系統響應時間與k值的關系Fig.5 Relationship between system response time and k value圖6 軌跡位置保護度與k值的關系Fig.6 Relationship between protection degree of track position and k value

在可接受的系統響應時間下，用戶軌跡位置保護程度是衡量算法優劣的的重要指標.圖6為本文基于交換查詢的軌跡隱私保護算法與CPP算法在用戶軌跡位置保護程度上的對比.

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

6 結束語

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