移動群智感知中融合數據的隱私保護方法

王濤春 金 鑫 呂成梅 陳付龍 趙傳信

(安徽師范大學計算機與信息學院 安徽蕪湖 241002)

(網絡與信息安全安徽省重點實驗室(安徽師范大學) 安徽蕪湖 241002)(wangtc@nuaa.edu.cn)

隨著集成多種傳感器(溫度傳感器、GPS、加速度傳感器、相機等)的移動智能設備(例如智能手機、智能手環等)的大量普及，一種新的傳感范式群智感知逐漸興起.群智感知[1]是一種利用便攜式移動智能設備攜帶的傳感器收集數據，然后將數據上傳給群智感知服務商，獲得一定的獎勵或應用.隨著移動智能設備集成的傳感器越來越多，群智感知收集的數據類型也越來越廣，使得應用領域更加廣泛.服務提供商利用參與者收集大量的信息向需求者提供服務，需求者利用這些信息進行分析解決問題[2-6]，例如交通導航、環境監測[7]、社區服務[8]等.

然而群智感知的應用也引出一系列隱私安全問題.例如攻擊者通過獲取參與者發送的醫療等敏感信息來推導參與者的健康狀況，從而進行一系列惡意攻擊.同時，參與者傳輸給應用服務器的數據帶有時空信息(參與者收集數據時的位置)，攻擊者可能利用這些時空信息推導出參與者的生活習慣、行為規律等敏感信息來進行惡意攻擊.因此，確保群智感知中參與者敏感信息的隱私是推動群智感知應用的關鍵因素.數據融合是群智感知數據收集的主要操作方式之一，目前群智感知中融合數據的隱私保護前提是服務提供商平臺是可信的，文獻[9]提出了一種基于同態加密的數據融合方案，該方案可以對密文進行融合操作，能夠有效進行各種數據融合(如均值、方差、偏差等)，然而第三方服務提供商能夠獲得每個節點的信息，所以該方案的應用前提是第三方是可信的.此外，現有的群智感知中隱私保護數據融合方法沒有考慮到節點(移動智能設備)移動性的特點，文獻[10]提出了一種基于Diffie-Hellman的加密方案，當節點加入或是失效時，需要更新所有節點的加密密鑰，節點的動態加入或失效處理復雜困難.

基于此，提出了群智感知中基于橢圓曲線的數據融合隱私保護算法(privacy preservation data aggre-gation algorithm based on elliptic curve cryptography, ECPPDA)，服務器對所有節點進行隨機分簇，簇內節點通過自身的公鑰構建簇公鑰，并利用簇公鑰對簇內節點采集到的數據進行加密，簇內節點對密文數據進行融合，最后將融合結果傳輸給應用服務器.應用服務器通過與簇內節點協作完成數據解密得到數據融合結果.由于應用服務器不能直接解密密文，從而保證節點數據的隱私性，解決了第三方必須是可信的應用場景.同時，ECPPDA算法中，節點的加入或失效只需要更新簇內節點的少量數據信息，因此本算法對節點動態加入或失效處理簡單，較適用于群智感知這類節點具有移動性特點的分布式網絡.理論分析和實驗結果表明ECPPDA不僅能夠保護用戶的數據隱私抵御共謀攻擊且兼顧節點移動性，而且能有效地降低節點的通信開銷.

1 相關工作

根據服務器收集的數據類型，群智感知數據收集分為2類：1)原始數據收集，移動智能設備直接上傳采集到的數據(如GPS坐標、加速度讀數等).2)融合數據，服務器需要得到區域內節點數據的融合結果(求和、平均值、方差等).例如，服務器通過獲得參與者平均運動量(步數、運動傳感器)能夠推導出參與者普遍的公共健康狀況.本文將這2類分別稱為基于原始數據的收集和基于融合數據的收集.當前國內外學者對群智感知中隱私保護問題進行了廣泛研究.現有方案主要利用4類方法[11]：分組統計、可信第三方驗證、k-匿名和數字加密.

基于分組統計的技術思想是參與者在上傳感知數據階段，將數據進行切片分成多個數據片，然后將數據片轉發給鄰節點，之后鄰節點上傳數據，應用服務器收集數據片并進行融合從而得到原始數據.文獻[12]提出了HP3(hot-potato-privacy-protection algorithm)方案，在服務器不可信的情況下實現保護隱私的分組轉發.HP3方案中參與者不是直接將數據上傳到服務器，而是將數據傳輸給參與者的一個朋友(可信)，朋友選擇另一個朋友并傳輸數據，以此類推，直到到達參與者定義的閾值，然后最后一個用戶將數據上傳到服務器.這種方案雖然解決了在服務服不可信情況下保證參與者的位置隱私，但前提是參與者有可信朋友.文獻[13]提出了一種基于編碼k-匿名方案(coding-based privacy preserving scheme)SLICER，SLICER集成了數據編碼技術和消息傳輸策略，以實現對參與者隱私的保護，同時保持高數據質量.SLICER方案沒有考慮共謀攻擊.文獻[14]提出了PEPPeR(privacy enhancing protocol for participatory sensing)方案，PEPPeR能夠保護查詢者的數據隱私，查詢者和參與者由可信第三方服務器分配令牌，查詢者和參與者傳輸數據時需要經過它們和第三方服務器之間的Tor(the onion router)網絡.這些方案的隱私保護全都需要可信的第三方，這種第三方更容易被攻擊.k-匿名是指區域內k個參與者和它們發出的信息不能被攻擊者區分出來.文獻[15]提出了AnonySense方案，該方案通過k-匿名技術來保護參與者的位置隱私.文獻[16]的作者利用可信的鄰居構建多個k-匿名區域發布虛假查詢，來防止攻擊者構建真實軌跡.數字加密是利用密碼學的知識對數據進行加密防止攻擊者竊聽參與者在傳輸時的數據內容.這4種技術常用來組合使用保護參與者的數據隱私.

針對群智感知中數據融合的隱私保護問題，近年來國內外學者已經提出了許多解決方案.文獻[17]提出的方案先利用多假名機制來克服由于參與者密度低而導致的漏洞，接著提出2種基于Paillier密碼系統的方法抵御sybil攻擊.文獻[10]提出了一種基于Diffie-Hellman的加密方案，但這些方案無法有效地支持動態連接和失效.以文獻[10]中的工作為例，當節點加入或失效時，需要更新所有節點的加密密鑰，這意味著群智感知應用程序具有高額的通信開銷.文獻[8]提出了一種基于同態加密的數據融合方案，該方案對密文能夠有效地進行各種數據融合(如均值、方差、偏差等)，然而第三方服務提供商能夠獲得每個節點的信息，所以該方案應用前提是具有可信的第三方.文獻[18]中提出了不需要可信第三方來保護融合數據隱私的協議，該協議通過節點間參數共享來抵御共謀攻擊.文獻[19]提出了2種具有隱私保護能力的加法融合數據方案：第1種方案是基于簇的隱私數據融合方案(cluster-based private data aggregation, CPDA),利用多項式的聚類協議和代數屬性完成隱私保護的數據融合;第2種方案是基于切片-混合的數據融合方案(slice-mix-aggregate, SMART),基于切片技術和加法關聯屬性.SMART方案的優點是計算開銷相對較少，但SMART對每個數據都分成多段，因此節點的通信開銷較大.文獻[20]提出了一種基于信任的數據融合方案ERTDA(energy-efficient reliable trust-based data aggregation)，ERTDA通過節點行為來計算和評估節點的信任值，并能夠及時檢測和排除受損節點.ERTDA能夠有效地提高融合數據的精確度，降低節點能耗，提高數據傳輸的可靠性，但節點信任值的評估以及受損節點的檢測需要大量的計算開銷，且ERTDA基于可信節點進行操作.

2 模型介紹

2.1 群智感知網絡框架

群智感知網絡主要由4個部分組成：移動節點、數據請求者、應用服務器和接入網絡，如圖1所示：

Fig. 1 Basic framework of the crowd sensing application

1) 移動節點(mobile node, MN).MN是具有感知、計算、存儲、通信等基本功能的移動智能設備，如智能手機、運動手環等.它們是群智感知網絡的基本單元，主要用于各類數據的采集，如溫度、濕度、位置、聲音等，并通過無線網絡將采集來的數據上傳到應用服務器.這些移動智能設備常由用戶隨身攜帶，所以能夠隨時隨地進行數據采集,在群智感知中也常被稱作參與者.

2) 數據請求者(data requester, DR).DR通過應用服務器發布感知任務，然后應用服務器將任務下達給參與者，服務器收集到請求者所需的數據時，將數據傳輸給請求者.在群智感知系統中參與者也可以通過他們的移動智能設備向服務器發布任務，所以參與者也可以是數據請求者.

3) 應用服務器(application server, AS).AS是對節點上傳的數據進行處理，如解密、分類、融合、存儲等，并與數據請求者實現數據的共享.根據移動節點提供的數據來回答數據請求者的各種問題，如請求者查找距離居住賓館最近的餐廳等.本文應用場景是最常見的半誠實模型，即參與者和服務器嚴格按照協議要求執行操作，另一方面，他們通過獲取信息推導出其他參與者的隱私信息.

4) 接入網絡.指數據傳輸的通道，通常是通過無線網絡進行數據傳輸的例如移動蜂窩網絡、藍牙、WIFI等無線網絡，目前感知網絡主要利用移動蜂窩網絡進行數據傳輸.

2.2 攻擊模型

根據攻擊來源可將攻擊劃分為2類：外部攻擊和內部攻擊.1)外部攻擊指的是攻擊者通過竊聽群智感知網絡獲取感知數據，破壞數據機密性.2)內部攻擊指的是群智感知網絡的參與者或服務提供商進行的攻擊，例如參與者獲取其他參與者的隱私信息，或服務提供商獲取參與者的隱私數據，并通過這些隱私信息進行惡意攻擊.本文主要采用的是半誠實模型，即群智感知中所有成員(服務提供商和參與者)嚴格執行設計的協議，但成員試圖通過協議執行過程獲得的數據來推導出其他成員的敏感信息.通過對傳輸數據加密能夠有效抵抗外部攻擊，而內部攻擊以及共謀(多個參與者或服務器與參與者)攻擊是ECPPDA研究的重點.

3 ECPPDA算法

本節主要介紹ECPPDA給出問題定義、算法思想，以及算法的具體執行步驟，最后對參與者的動態加入和失效處理過程進行描述.

3.1 問題定義及算法思想

ECPPDA假設有m個參與者和1個應用服務器，參與者采集感知數據、加密并融合，應用服務器得到融合后的密文數據，參與者ni采集的感知數據為di(i=1,2,…,m).

3.2 ECPPDA算法步驟

ECPPDA融合參與者采集到的感知數據，其處理主要包括3個階段：

2) 數據傳輸.簇頭節點隨機選擇簇內某個節點作為簇頭節點，簇頭節點隨機選擇一個始節點，始節點通過簇公鑰加密自身的感知數據并將密文傳輸給中間節點，中間節點接收到前一個節點發送的密文并與自己的密文融合，再將融合結果發送給下一個中間節點，以此繼續，直至終節點得到簇內所有節點密文的融合結果并發送給服務器.

3) 解密.服務器接收每個簇的密文融合結果后，需分別與每個簇內節點協同合作計算得到簇融合結果的明文，最后服務器對所有的簇明文進行融合從而得到所需數據.

3.2.1 初始化

簇劃分具體過程為：在任務區域內接受任務節點ni發送公鑰Yi給服務器，服務器隨機選擇k個節點形成一個簇，從而將任務區域劃分為g個簇，并給每個簇隨機選擇一個節點作為簇頭節點.對于每個簇，服務器對簇內k個節點的公鑰進行融合形成簇公鑰，然后將簇公鑰和簇信息(包括簇頭節點和簇成員信息)發送給簇內的所有節點.其操作包括3個步驟：

具體過程見算法1.

算法1.節點分簇.

① for(i=1;i≤n;i++)*節點ni操作*

③Yi=xi×G;

④Yi→NAS;*將公鑰Yi發送給應用服務器NAS*

⑤ end for

⑥ for(i=1;i≤g;i++)*服務器操作*

⑦ 簇Ci={n1,n2,…,nk};*隨機選擇k個節點構成簇Ci*

⑨ 隨機選取簇頭節點nh;

⑩ 簇Ci:DCi→節點ns,ns∈Ci;*包括簇公鑰和簇頭等分簇信息DCi發送給簇內所有成員節點*

3.2.2 數據傳輸

每個簇的操作相同，現以一個簇操作為例介紹數據傳輸進程.節點ni通過簇公鑰PCK加密它的數據di，簇頭節點隨機選擇一個節點作為始節點(密文發送的初始節點)，始節點將密文發送給隨機選擇的下一個節點(中間節點)，中間節點接收始節點的密文并與自身的密文進行融合，再發送給下一個中間節點，如此繼續，直至簇內所有節點完成密文融合，最后一個節點(終結點)把最終的融合結果發送給服務器.

節點ni的感知數據為di，橢圓曲線參數為E(Fp)，階數為q，G是基點.節點ni選擇一個隨機數xi作為節點的私鑰，然后計算節點ni的公鑰Yi=xi×G.E(Fp)，q，G是群智感知中公共參數，并廣播給簇內所有成員.

步驟2. 簇頭隨機選擇一個成員節點ni(i=1,2,…,k)為始節點，并通知節點ni.以此，可以將節點分為始節點、中間節點和終節點.

3.2.3 解密

服務器接收到簇Ci發送過來的密文數據后，首先與簇成員協同合作計算Di，進而計算得到簇明文的融合結果Sumj，最后對所有簇數據進行融合得到任務區域內所有節點的數據融合結果Sum.每個簇Ci的密文解密步驟為：

步驟1. 服務器把簇融合密文中的Ca廣播給簇內所有成員節點ni(i=1,2,…,k).

步驟2. 節點ni計算Di=xi×Ca并以密文傳輸的方式將Di傳輸給服務器.

(1)

式(1)的正確性證明：

證畢.

群智感知中所有數據通過無線傳輸，且參與節點具有動態性特征，數據傳輸過程中出現數據丟失是普遍情況.ECPPDA采用簡化的超時重傳機制來處理傳輸過程中數據丟失情況.重傳機制的主要思想為：數據傳輸過程中，當數據接收者收到數據時要立刻返回一個確認信息給數據發送者，如果數據發送者的重傳超過時間(retransmission time out， RTO)T，即在時間T內沒有收到數據接收者的確認信息則默認為數據丟失，再次發送一份相同的數據.其中T=2TR，TR為數據在2個端點平均往返時間.簡化的超時重傳機制能夠弱化網絡傳輸中的各種復雜問題.

3.3 節點加入和節點失效

群智感知是一種特殊的無線傳感器網絡，它的節點由移動智能設備構成，而設備持有人由于自身原因離開任務區域或關閉移動智能設備，所以與傳統的無線傳感器網絡相比，群智感知節點具有更顯著的移動性特征，而現有的方法很少考慮群智感知節點移動性特征.基于此，ECPPDA考慮節點移動性特征，更加方便快捷處理節點的加入和節點失效情況.

3.3.1 節點加入

算法2.節點加入.

① 輸入b;*其中b是加入任務的節點數*

② for (i=1;i

④Yi=xi×G;*計算節點ni公鑰*

⑤Yi→NAS;

⑥ end for

⑦ if(b<γ×n+2)*判斷加入節點數是否超過下限*

⑧ 查詢并選擇節點數量最少的簇Ci;

⑨ if (b+|Ci|<2×γ×n+4)*|Ci|為簇Ci內節點數量*

3.3.2 節點失效

簇Ci內節點ni失效有2種情形：

1) 主動失效即節點ni失效前向服務器發送離開信息.節點ni發送離開信息給服務器申請離開簇，服務器接收信息后查看簇Ci內剩余成員節點的數量，當剩余成員節點數量大于γ×n+2時，服務器計算新的簇公鑰PCK=PCK-Yi，并隨機選取簇頭，更新簇Ci內剩余成員節點的簇信息.當剩余成員節點數量小于γ×n+2時，服務器解散簇Ci，然后將該簇剩余節點按照流程加入到其他簇.

2) 被動失效節點ni沒有發送任何信息就離開簇.簇Ci的節點ni被動失效有2種假設：①假設節點ni在接收數據前失效，節點nj傳輸數據給節點ni，節點ni已經失效無法返回確認信息給節點nj.由于超時重傳機制，節點nj將不停地傳輸數據直到重傳次數達到設置的閥值(超時重傳機制中最大重傳次數)時節點ni沒有發送返回信息則認為節點ni失效，然后節點nj向服務器發送信息表示節點ni失效，服務器接收信息后按照節點失效情形1)的方式更新簇信息.②假設節點ni在接收信息后失效，節點ni失效無法繼續傳輸數據，因此服務器不能接收簇Ci的數據，服務器對簇Ci內節點進行失效查詢(服務器向簇Ci內所有節點發送信息，沒有響應的節點被確認為失效節點)，確定失效節點ni后服務器按照節點失效情形1的方式進行處理.

4 性能分析

本節ECPPDA算法與現有算法在應用環境、算法的安全性和復雜度等方面進行分析.

4.1 應用環境

應用環境主要從第三方是否確定可信、能否抗共謀攻擊、節點動態性、數據丟失處理以及數據實用性等方面進行對比.從表1可以看出，與PDAIF[22](private data aggregation with integrity assurance and fault tolerance)相比，ECPPDA可以抵御共謀攻擊且不需要可信的第三方平臺；與CTPPSP[18](collusion-tolerable privacy-preserving sum and product calculation)相比，ECPPDA對數據丟失進行了處理，提高了方案的健壯性，且ECPPDA沒有降低數據實用性且保留了節點移動性的特征.

Table 1 Comparison in Advantages and Disadvantages of Existing Schemes

4.2 安全性分析

本節對外部攻擊、內部攻擊和共謀攻擊3方面進行安全性分析.

1) 外部攻擊

2) 內部攻擊

3) 共謀攻擊

4.3 復雜度分析

群智感知中參與節點資源通常相對受限，而服務器資源比較豐富，所以本文主要考慮節點的資源消耗情況.ECPPDA算法主要由3個部分組成：初始化、數據傳輸、解密.初始化階段節點經過計算得到公鑰，然后傳輸公鑰和分簇信息給服務器以完成節點分簇，所以初始階段單個節點的時間與空間復雜度為O(1)，通信量為O(|G|)(|G|表示基點G的點長)，因此，群智感知網絡在初始化階段時間與空間復雜度為O(n)以及總通信量為O(n|G|)；數據傳輸階段，每個節點需完成一次數據加密和密文融合，并將融合密文傳輸給下一節點，所以此該階段單個節點的時間與空間復雜度分別為O(1)和O(|G|)，通信量為O(|G|)，該階段網絡總的時間與空間復雜度分別為O(n)和O(n|G|)，總通信量為O(n|G|)；解密階段，節點通過服務器發送的聚合密文(Ca,Cb)計算得到Di并傳輸給服務器，所以解密階段單個節點的時間與空間復雜度分別為O(1)和O(|G|)，以及通信量為O(|G|).綜上分析，ECPPDA算法總的時間與空間復雜度分別為O(n)和O(n|G|)，群智感知網絡總通信量為O(n|G|).

5 實驗與結果實驗評估

實驗環境為Win7 OS，Intel Core i5 CPU和16 GB內存，采用GeoLife項目[18,24]中的公開數據點來對本文提出的方案進行評估.該公開數據點是由不同的GPS記錄器每間隔5～10 m或者2～5 s采集的.隨機選擇中間的70個數據點，經過相應的坐標放大變換轉化為2維相對坐標.為了對算法的通信量和隱私性能進行比較，下面對PDAIF[22]算法和ECPPDA算法進行仿真實驗對比.

圖2給出了2種算法在簇內節點數目k不同時節點的通信量比較，由于PDAIF算法通過未來消息緩沖機制保證容錯性，節點每次傳輸的是2份數據，且在構建簇時預先在服務器緩存B個備份數據，所以ECPPDA方案可以有效地降低節點的通信消耗.

Fig. 2 Communication overhead with different number of nodes

圖3給出了在惡意節點概率為10%時，不同簇節點數目下任意節點的數據隱私泄露概率，即攻擊者通過第三方服務器和惡意參與者進行共謀攻擊，解密單個節點數據的概率，由于PDAIF協議沒有考慮共謀攻擊，當簇內節點越多時，共謀攻擊情況下單個節點數據隱私泄露的概率就越高.ECPPDA方案通過簇內所有成員共同協作進行密文解密的方式來抵御共謀攻擊，其次通過數據加密抵御外部竊聽攻擊來保證數據的機密性，所以ECPPDA方案可以有效地保護節點數據的隱私.

Fig. 3 The leakage probability of single node

Fig. 4 The leakage probability of cluster

圖4給出了簇內成員節點數目不同時(惡意節點概率為10%)，簇內所有節點的感知數據發生隱私泄露的概率，即攻擊者通過服務器和惡意參與者進行共謀攻擊，獲得簇內誠實節點的感知數據的概率，由于PDAIF算法沒有考慮共謀攻擊，僅與左右鄰居節點交換參數，因此當攻擊者與目標節點的左右鄰節點進行共謀就能獲得該節點的感知數據.ECPPDA算法中每個節點數據的解密需要簇內所有節點協同合作，因此ECPPDA算法中節點數據發生隱私泄露的概率遠遠低于PDAIF算法，如圖4所示.

由安全性分析可知只要簇內節點數量不小于k時，所有節點數據泄露概率可忽略不計，即使不滿足節點數量要求，節點數據泄露的概率也較低，特別當簇內節點數量超過6時，節點數據發生隱私泄露概率幾乎忽略不計.當簇內節點數為2時，單個節點數據泄露概率較高，因為只要有1個惡意節點就會導致數據泄露.如圖5所示：

圖6給出簇內成員節點數初始值k不同情況下，新加入節點數b不同時需要更新簇公鑰的節點數量.由圖6可知，當加入節點數量小于簇內成員節點數量時，需要更新的節點數量為簇內成員節點數，因為加入的節點會選擇1個簇加入然后管理器需要更新該簇內原有節點的公鑰.當加入節點數量大于簇內節點k值時，需要更新的節點數為0，因為加入節點會選擇建立新簇，因此不會影響到原有節點.

6 總 結

群智感知中設計具有高安全、高效率、高質量隱私保護的融合數據方案是一個挑戰性的問題.本文提出了一種具有隱私保護的融合數據算法ECPPDA.ECPPDA通過服務器構造多個簇，然后簇節點利用簇公鑰加密數據并在簇內融合傳輸，直到最后1個簇節點將融合數據上傳至服務器，服務器通過與簇的所有成員協同合作簇融合密文進行解密，并對所有簇的數據進行融合得到任務區域內所需的融合數據.數據傳輸過程中采用超時重傳機制來解決數據丟失問題.由于密文是通過多方協同合作進行解密，所以ECPPDA可以抵御共謀攻擊.理論分析和實驗表明ECPPDA算法能夠保護每個參與者數據的隱私性，顯著降低了參與者的通信開銷，并保證了數據的實用性.