Paillier 加密的隱私保護群智感知任務發布算法

田 靜，杜云明，李 帥，劉 義

佳木斯大學 信息電子技術學院，黑龍江 佳木斯 154000

隨著無線通信技術的發展以及5G 通信的正式商用，智能手機等移動通信感知設備越來越廣泛地應用在各行各業，這些嵌入大量傳感器（GPS、溫感、陀螺儀等）的移動設備令群智感知收集信息成為可能。通常，群智感知指利用移動設備的感知能力，通過發放激勵從移動設備、移動設施獲得所需數據信息的分布式數據獲取方法。這種數據收集方法具有數據收集者無需到達現場，可從參與感知用戶獲得感知結果，且能夠獲得實時反饋，減少了數據收集過程中的投入消耗等一系列優勢。

但這種感知方式存在不可忽視的隱私安全隱患。例如：某用戶需獲得某一確定感知區域內的溫度變化，因而將這一任務以及感知區間通過授權機構或發布平臺發布給廣大用戶，并由這些位于感知區域內的用戶將感知結果反饋給任務發布者。在這一過程中，任務發布者的感知位置信息、任務申請者的所在位置信息等都會暴露給彼此和授權機構。當部分實體不可信時，將會造成用戶隱私的泄露。針對群智感知過程中存在的隱私泄露問題，Yang 等人從感知用戶分布密度出發，利用差分隱私保護模型提出一種移動感知的位置隱私保護策略。但添加噪聲的方式可能會造成反饋結果精確度不足的問題。其后，Yang 等人又利用分布式共識的區塊鏈完成隱私保護的群智感知任務發布。而這種協作方式可能會因用戶協作意愿而降低隱私保護成功率。近年來，一些隱私保護的群智感知應用，諸如共享公交、稀疏感知、鄰近感知和成員推薦等一系列方法被相繼提出。

雖然上述方法在很大程度上能夠保護群智感知過程中的用戶隱私，但是并未真正實現整個群智感知環境中所需要的多實體之間的信息閉環，即上述方法有的假設授權機構的完全可信（如共享公交、稀疏感知需要通過可信平臺提供隱私保護處理），有的僅針對任務申請者的隱私安全（如鄰近感知和成員推薦未能考慮任務發布者同樣不希望發布的任務信息被不能反饋結果的用戶獲得）。針對這種群智感知過程中三方實體能夠彼此獲取隱私信息的問題，基于同態加密思想和環境網格劃分，本文提出了基于Paillier 加密的隱私保護群智感知任務發布算法。

1 預備知識

1.1 系統架構

通常，群智感知的任務發布過程由圖1 所示的三個實體完成，即在群智感知系統架構中存在任務發布者、授權機構和任務接收者三個實體。任務發布者指具有感知需求，并將該請求發送給授權機構，由授權機構發布任務并回收感知結果后返還給該實體；授權機構可視為任務發布和申請者之間的連接機構，由該實體完成任務位置區間的匹配計算、任務發布、激勵發放等信息交換操作和計算；任務申請者是群智感知的主體，由該實體完成對所需任務、確定位置的信息感知，并將結果反饋給授權機構。

圖1 群智感知的系統架構Fig.1 System architecture of crowdsensing

按照圖1 所示的系統架構，可知在這種系統架構中完成一個群智感知任務的發布和回收存在三個實體之間隱私信息泄露的風險。而位置隱私的泄露普遍存在于群智感知任務發布過程中，并表現為授權機構能夠精確獲得任務申請者和發布者兩方的位置信息；任務申請者可在獲得任務發布者需求位置后構建虛假反饋結果；任務發布者惡意獲得大量任務申請者位置信息并隨意發布。因此，在群智感知系統下，存在較為復雜的隱私泄露風險，需要提供一種能夠同時保障三方實體均無法有效獲取各方精確位置的任務發布方法。

1.2 Paillier 密碼體系

要滿足三方之間的位置信息不被任一實體所獲得，且實現位置隱私環境下的任務分配，最好的解決方法是找到一種隱私環境下的計算策略，通過秘密位置匹配計算完成任務發布。在秘密隱私計算前提下，同態加密是一個很好的密態計算方式。Paillier密碼體系則能夠提供同態加密計算的各種同態特性。其計算處理如下：

其解密過程為，對于密文，存在是(-1)和(-1)的最小公倍數，即=lcm((-1),(-1))，此時有明文：

基于這樣一種密態環境下的加法計算，可設計一種基于該技術的群智感知任務分配方法。

2 基于Paillier 加密的任務發布

2.1 隱私保護算法的基本思想

在群智感知任務發布中，可將待感知區域劃分為一個包含多個單元格的網狀區域。此時位于每個單元格中的用戶為備選任務申請者，當這一用戶同意為任務發布者反饋感知結果時，可將所在區域的感知結果反饋給任務發布者。在這一過程中，授權機構完成對任務的發布以及反饋結果的收集工作。

因此，隱私保護的基本思想可歸結為：（1）任務發布者和任務申請者首先對任務所需感知區域以及提供感知反饋區域按照預定要求設置位置取值；（2）這兩個實體對設置完的取值使用相同的Paillier 公鑰進行加密后并發送給授權機構；（3）授權機構在密態環境下對上述兩個實體提交的結果進行匹配計算，若滿足條件則由當前的申請者集合提交結果，并將結果反饋給任務發布者；（4）任務發布者按照收到的反饋信息對任務申請者發放感知激勵。在這一過程中，授權機構所獲得的全部信息為加密后的密態信息，在不知道Paillier 私鑰的前提下無法獲知具體感知區域；任務發布者不知道任何任務申請者的具體位置，最后獲得的是整個區域的感知結果；而任務申請者同樣不知自身是否位于感知區間，因而無法獲知任務發布者的位置隱私。

2.2 隱私保護的群智感知任務發布流程

授權機構首先將所管轄范圍劃分為由多個單元格構成的網絡區域，并將該區域在這一范圍內廣播，使得任務發布者和任務申請者均能獲得這一區域的網格劃分。

任務發布者從授權機構獲得當前所在區域的網格劃分，選擇包含所需感知區域在內的一個矩形子區域，并基于該區域建立對應的二維矩陣（如式（4）所示）。其中，需要感知的網格在二維矩陣中標記為任意非0 數字，而不需感知的網格標記為0。在完成二維矩陣的建立之后，使用Paillier 公鑰對矩陣中每個標記值進行加密，在加密完成后將加密后的矩陣以及激勵保障金一同發送給授權機構。

授權機構在收到任務發布者發送過來的由感知區域構成的二維矩陣后，將感知區域框架廣播給任務申請者。

任務申請者同樣從授權機構獲得所在區域的網格劃分以及任務發布者的感知區域，首先核對自身的感知區間是否包含任務發起者所需的感知網格。若有，則按照任務發布者的感知區域構建自身的反饋區域，并基于該區域建立二維矩陣（如式（5）所示）。使用非0 數值標記能夠感知的單元格，而不能感知的標記為0。同時，將建立后的二維矩陣發送給授權機構。

授權機構獲得由多個任務申請者發送過來的感知矩陣，在剔除掉相同矩陣后獲得申請矩陣集合B,0 ≤≤（為任務發布者可發放激勵的最大值）。在計算=·+·+…+·B后，將發送給任務發布者。式（6）給出了由式（4）、式（5）經過計算后的結果。

任務發布者使用Paillier 私鑰對進行解密，若解密后的矩陣包含所有需要感知的單元格，則通知授權機構獲取感知結果；否則要求授權機構再次向申請者廣播感知區域。授權機構將感知結果發送給任務發布者，同時將激勵保障金按照預先設定分發給各個任務申請者。

在不考慮Paillier 加密的情況下，設中非零元素為需要感知的區域單元格，中非零元素為任務申請者能夠感知的區域單元格，·之后獲得的結果中非零元素則為兩個實體可感知的匹配區域。當任務發布者綜合多個任務申請者反饋的匹配區域之后，就可以找到能夠反饋所有需要感知區域的任務申請者，此時可保障感知任務的順利發布。

2.3 任務發布者的信息處理

設任務發布者建立對應的二維矩陣中，每個矩陣對應的元素可表示為a,0 ≤,≤，根據Paillier密碼體系加密獲得每個矩陣元素對應的加密后元素信息(a)，并將(a)發送給授權機構。算法1 描述了這一處理過程。

任務發布者的加密矩陣建立

如何建立Paillier 密碼系統的公鑰在1.2 節中已經詳細介紹，此處不再贅述。經過算法1 的處理可獲得加密后的任務發布者位置網格二維矩陣()，并將該矩陣發送給授權機構。

2.4 任務申請者的信息處理

設任務申請者通過廣播獲得任務發布者公鑰=(,)，同時按照自己能夠完成的任務位置網格區間建立自身的位置響應二維矩陣，其中每個矩陣中對應的元素為b,0 ≤,≤，使用對每個元素加密后獲得(b)，并將(b)發送給授權機構。算法2 給出了這一加密過程。

任務申請者的加密矩陣建立

不同的任務申請者使用算法2 對自身位置矩陣加密后，分別將加密矩陣發送給授權機構，授權機構將通過矩陣計算完成加密狀態下的位置匹配。

2.5 授權機構的信息處理

授權機構是完成秘密位置矩陣匹配的中心實體，當該實體收到由多個任務申請者發送的服務位置矩陣以及由任務發布者發送的任務矩陣之后，計算=·+·+…+·B獲得同態加密計算后的矩陣(c)，并將(c)反饋給任務發布者，由任務發布者解密后檢驗當前矩陣是否滿足任務要求。

隱私保護的任務位置匹配

任務發布者在收到反饋的(c)后對其進行解密處理，若該矩陣中與初始的中每個對應位置中的元素均為非零元素，則當前矩陣可提供所有感知結果，否則不能提供全部位置感知，需要由授權機構完成二次任務申請者申請匯總，以找到足夠位置的任務申請者用來完成群智感知任務。

3 安全性分析

由于在群智感知的任務發布過程中，存在兩個實體提交自身信息的情況，所有在安全性分析中需要同時考慮任務發布者的安全性以及任務申請者的安全性，即這兩個實體的信息是否會被另外參與發布的兩個實體所獲知。

3.1 任務發布者的安全性

任務發布者在整個群智感知過程中的位置隱私安全主要存在兩方面的威脅，即授權機構和任務申請者，并表現為授權機構需要核定任務發布者的位置是否和任務申請者位置一致；另一方面，任務申請者也需要確認是否能夠參與任務感知。對于授權機構，其獲得的任務發布者信息是加密后的矩陣()，在不具有私鑰=(,)的前提下，授權機構無法獲知矩陣中具體位置數值。同時，由于任務發布者建立的矩陣中使用的數值并不是完全一致的，即使授權機構掌握其公鑰也不能通過碰撞性嘗試猜測矩陣中具體信息。

3.2 任務申請者的安全性

對于任務申請者位置，需要保障授權機構和任務發布者不會獲得其精確位置。其中，由于任務申請者同樣使用任務發布者公開的公鑰對自身位置矩陣進行加密，授權機構在不具有私鑰的情況下不能通過解密獲得任務申請者精確位置信息。

而對于任務發布者，申請者的信息以及位置加密矩陣(b)并不被任務發布者所獲知，整個過程中任務發布者僅可知，當前提供的加密位置矩陣()能夠被加密矩陣(b)所匹配。此外，加密矩陣(b)是哪一個具體的任務申請者所提供，且每一個任務申請者能夠提供哪個感知位置的任務反饋，這些信息都是授權機構在加密狀態下通過Paillier 秘密系統的同態特性，在密態環境下通過矩陣點乘來完成計算的。因此整個過程中，任務發布者并不能獲得任務申請者任何準確的位置信息。

因此，在整個群智感知的過程中，三方實體之間均不存在過多獲取其他實體位置信息的情況，因而能夠實現隱私保護下的群智感知的任務發布。

4 實驗驗證

4.1 實驗設定

為驗證算法的有效性和隱私保護能力，本文在模擬環境下對該算法和其他同類算法進行測試比較，其結果進一步支持在安全性分析中所獲得的結論。模擬實驗在筆記本電腦I7 處理器、8 GB 內存的環境下，使用Python 3.6 進行測試。測試使用Geolife提供的位置數據，選擇同一區域進行網格劃分，并假定每10 個用戶中存在一個可反饋感知結果的任務申請者。參與比較的算法有基于差分隱私的DPLP（differential privacy-based location protection）算法、基于可調節路徑的PAPP（preserving adjustable path privacy）算法以及基于差分和位置扭曲的Differential-distortion算法。因此，模擬實驗結果將在與上述同類算法的比較和分析中給出。在算法有效性方面將從算法執行時間、感知位置匹配率以及反饋結果正確率等方面加以驗證。算法隱私保護能力將從實體間數據披露程度（信息熵）和匹配位置猜測成功率兩方面加以驗證。

4.2 實驗結果及成因分析

在算法有效性方面，主要驗證算法與其他同類算法在時間、任務匹配以及結果準確性方面的能力。通常，在群智感知中，算法的執行時間是按照發布感知到反饋結果的整個處理過程。在模擬實驗中，假設選定的用戶都是可以反饋感知結果的用戶，圖2 給出了不同算法在執行時間上的差異。從該圖中可以看出，本文算法盡管采用了加密措施來完成各個申請用戶與發布用戶之間的區域匹配，但加密過程可以在線下進行，授權機構僅需要進行有限的加密后同態計算即可完成匹配過程。此外，該算法執行時間較短還包括以下原因：首先，矩陣計算是利用矩陣點乘的方法計算的，并沒有達到的三次方這樣高的復雜度；其次，矩陣計算關注點是非零元素的個數而不是具體非零元素的值，因此使用異或運算可代替乘法運算，而異或運算的計算耗時極低；最后，用于分配任務的網格規模有限，進而導致使用的矩陣規模較小，這也是計算開銷較低的一個原因。而其他算法或者添加了滿足差分隱私的噪聲數據影響匹配結果，或者對整個感知過程中的數據傳遞進行了路徑傳遞變化，因而任務申請者的自身位置是經過各種變化處理的，這種變化擾亂了匹配的真實性，在很大程度上存在匹配冗余，這種冗余增加了算法處理時間，因而這些算法的執行時間要高于本文算法。

圖2 不同算法的執行時間Fig.2 Running time of various algorithms

圖3 給出了不同算法感知位置的匹配成功概率。從該圖中可以看出，本文算法不僅具有較高的感知匹配率，且這種匹配率能夠保持均衡穩定。這是由于本文算法并未對申請用戶以及任務發布用戶進行噪聲與扭曲處理，所有操作均在原始位置區間通過同態加密特性完成匹配操作，因而相對于其他通過添加噪聲、位置變換、位置扭曲等算法具有更好的感知匹配率。

圖3 不同算法的感知位置匹配率Fig.3 Matching probability of crowdsensing locations of various algorithms

圖4 不同算法的反饋結果正確率Fig.4 Accuracy of feedback results of various algorithms

圖4 給出了不同算法獲得由任務申請者反饋結果產生的結果正確率。同樣由于本文算法采用的位置匹配特性，使得任務申請者反饋的結果能夠真實地反映任務發布者所需要的任務集合，因而本文算法的反饋結果正確率最高。而其他幾種算法則由于位置扭曲，造成部分結果不準確的情況，影響結果反饋。

在算法隱私保護能力方面，將從攻擊者對各實體位置猜測的成功率以及成功率基礎上由信息熵表示實體間信息披露兩方面加以驗證。

圖5 給出了攻擊者對各個實體位置猜測的成功率。從該圖中可以看出，已有算法在任務申請者數量增加的情況下，被攻擊者準確識別猜測的概率逐漸降低，這是由于任務申請者用戶數量增加產生了泛化作用，而這種泛化增加了準確猜測的難度。但是，本文算法由于采用加密手段，在密態環境下完成任務匹配發布，整個過程中并沒有任何位置信息被明文使用，因此具有更為嚴格的隱私保護效果，攻擊者猜測成功的概率最低，且并不因任務申請者數量而有所變換。

圖5 不同算法猜測實體位置的成功率（攻擊者）Fig.5 Success ratio of guessing real locations of various algorithms(adversary)

圖6 不同算法的實體間信息披露Fig.6 Entropy of information disclosure of various algorithms

綜上，通過與同類算法在有效性和隱私保護能力兩個主要方面的比較，可以看出本文算法具有一定優勢，優于目前主流算法。

5 結束語

對于群智感知的任務發布隱私問題，本文提出了一種在Pailier 加密基礎上利用位置區域網格矩陣完成密態下的任務發布算法。該算法能夠有效保障群智感知參與各方實體之間的隱私不會在感知過程中被泄露。同時，通過安全性分析和在模擬環境的實驗驗證進一步證明了所提出的算法的優越性。

盡管本文算法很好地解決了群智感知任務發布過程中的位置信息隱私保護的問題，但該算法存在一些問題未能有效解決。如感知用戶不能滿足所需區間情況下，再次發布任務的頻率問題以及感知過程中結果反饋中可能存在的任務申請者造假問題。今后的工作將主要解決這兩個問題。